#include #include #include #include #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 graph[N + 1]; vector C(M); vector u(M), v(M); for (int i = 0; i < M; ++i) { cin >> C[i]; } for (int i = 0; i < M; ++i) { cin >> u[i] >> v[i]; graph[u[i]].push_back({v[i], C[i]}); graph[v[i]].push_back({u[i], C[i]}); } // dist[node][used_coupons] = min cost to reach 'node' using 'used_coupons' vector> dist(N + 1, vector(K + 1, INF)); priority_queue, vector>, greater<>> pq; dist[1][0] = 0; pq.push({0, 1, 0}); // {cost, node, used_coupons} while (!pq.empty()) { auto [cur_cost, node, used] = pq.top(); pq.pop(); if (cur_cost > dist[node][used]) continue; for (const auto& e : graph[node]) { // クーポンを使わない if (dist[e.to][used] > cur_cost + e.cost) { dist[e.to][used] = cur_cost + e.cost; pq.push({dist[e.to][used], e.to, used}); } // クーポンを使う if (used < K && dist[e.to][used + 1] > cur_cost) { dist[e.to][used + 1] = cur_cost; pq.push({dist[e.to][used + 1], e.to, used + 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; }