#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll LLINF = 1LL << 60;

int main() {
	int N, M, K;
	cin >> N >> M >> K;
	vector<ll> C(M);
	for(auto& e : C) cin >> e;
	vector<vector<pair<int, ll>>> G(N);
	for(int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		G[u].emplace_back(v, C[i]);
		G[v].emplace_back(u, C[i]);
	}
	vector<vector<ll>> dp(N, vector<ll>(K + 1, LLINF));
	using Data = tuple<ll, int, int>;
	priority_queue<Data, vector<Data>, greater<Data>> que;
	que.emplace(0, 0, K);
	dp[0][K] = 0;
	while(!que.empty()) {
		auto [d, u, rem] = que.top();
		que.pop();
		if(dp[u][rem] < d) continue;
		for(auto [v, w] : G[u]) {
			if(dp[v][rem] > d + w) {
				dp[v][rem] = d + w;
				que.emplace(dp[v][rem], v, rem);
			}
			if(rem > 0 and dp[v][rem - 1] > d) {
				dp[v][rem - 1] = d;
				que.emplace(dp[v][rem - 1], v, rem - 1);
			}
		}
	}
	ll ans = *min_element(dp[N - 1].begin(), dp[N - 1].end());
	if(ans == LLINF) ans = -1;
	cout << ans << endl;
}