#include using namespace std; using ll = long long; const ll INF = 1e18; int main() { int N, M, K; cin >> N >> M >> K; vector C(M); for (int i = 0; i < M; ++i) { cin >> C[i]; } vector>> adj(N + 1); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; adj[u].emplace_back(v, C[i]); adj[v].emplace_back(u, C[i]); } vector> dist(N + 1, vector(K + 1, INF)); priority_queue>, vector>>, greater<>> pq; dist[1][K] = 0; pq.emplace(0, make_pair(1, K)); while (!pq.empty()) { auto [current_cost, state] = pq.top(); auto [u, k] = state; pq.pop(); if (current_cost > dist[u][k]) continue; for (auto [v, c] : adj[u]) { if (dist[v][k] > current_cost + c) { dist[v][k] = current_cost + c; pq.emplace(dist[v][k], make_pair(v, k)); } if (k > 0 && dist[v][k-1] > current_cost) { dist[v][k-1] = current_cost; pq.emplace(dist[v][k-1], make_pair(v, k-1)); } } } ll ans = INF; for (int k = 0; k <= K; ++k) { ans = min(ans, dist[N][k]); } if (ans == INF) { cout << -1 << endl; } else { cout << ans << endl; } return 0; }