#include using namespace std; using ll = long long; const ll INF = 1LL << 60; struct Edge { int to; ll cost; }; int main() { int N, M, K; cin >> N >> M >> K; vector C(M); for (int i = 0; i < M; ++i) { cin >> C[i]; } vector> G(N + 1); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; G[u].push_back({v, C[i]}); G[v].push_back({u, C[i]}); } vector> dist(N + 1, vector(K + 1, INF)); dist[1][0] = 0; using T = tuple; priority_queue, greater<>> pq; pq.emplace(0, 1, 0); while (!pq.empty()) { auto [cost, now, used] = pq.top(); pq.pop(); if (dist[now][used] < cost) continue; for (auto& e : G[now]) { if (dist[e.to][used] > cost + e.cost) { dist[e.to][used] = cost + e.cost; pq.emplace(dist[e.to][used], e.to, used); } if (used < K && dist[e.to][used + 1] > cost) { dist[e.to][used + 1] = cost; pq.emplace(cost, e.to, used + 1); } } } ll ans = *min_element(dist[N].begin(), dist[N].end()); if (ans == INF) cout << -1 << endl; else cout << ans << endl; }