#include <iostream>
#include <vector>
#include <queue>

using P = std::pair<long long, long long>;

std::vector<std::vector<P>> G;

int main(){
	int N, M, K;
	std::cin >> N >> M >> K;
	G.resize(N);
	int C[M];
	for(int & c : C) std::cin >> c;
	for(int m = 0, u, v; m < M; ++m){
		std::cin >> u >> v;
		u--, v--;
		G[u].emplace_back(v, C[m]);
		G[v].emplace_back(u, C[m]);
	}
	std::vector<std::vector<long long>> D(K + 2, std::vector<long long>(N, INT64_MAX));
	for(int k = 0; k <= K; ++k){
		D[k + 1][0] = 0;
		char visited[N];
		std::fill(visited, visited + N, false);
		std::priority_queue<P, std::vector<P>, std::greater<P>> que;
		que.emplace(0, 0);
		do{
			int me = que.top().second;
			que.pop();
			if(visited[me]) continue;
			visited[me] = true;
			for(const auto & p : G[me]){
				long long cost = std::min(D[k][me], D[k + 1][me] + p.second);
				if(cost < D[k + 1][p.first]){
					D[k + 1][p.first] = cost;
					que.emplace(cost, p.first);
				}
			}
		} while(!que.empty());
	}
	if(D[K + 1][N - 1] == INT64_MAX){
		puts("-1");
	}
	else{
		std::cout << D[K + 1][N - 1] << std::endl;
	}
	return 0;
}