#include using namespace std; using ll = long long; using P = tuple; // {cost, node, used_coupon} const ll INF = 1LL << 60; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, K; cin >> N >> M >> K; vector C(M); for (int i = 0; i < M; ++i) cin >> C[i]; vector>> graph(N); // graph[u] = {v, cost} for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; --u; --v; graph[u].emplace_back(v, C[i]); graph[v].emplace_back(u, C[i]); } // dist[node][used_coupon] = 最小コスト vector> dist(N, vector(K + 1, INF)); dist[0][0] = 0; priority_queue, greater

> pq; pq.emplace(0, 0, 0); // {cost, node, used_coupon} while (!pq.empty()) { auto [cost, node, used] = pq.top(); pq.pop(); if (dist[node][used] < cost) continue; for (auto [nei, c] : graph[node]) { // クーポンを使わない場合 if (dist[nei][used] > cost + c) { dist[nei][used] = cost + c; pq.emplace(cost + c, nei, used); } // クーポンを使う場合(残っていれば) if (used < K && dist[nei][used + 1] > cost) { dist[nei][used + 1] = cost; pq.emplace(cost, nei, used + 1); } } } ll ans = *min_element(dist[N - 1].begin(), dist[N - 1].end()); cout << (ans == INF ? -1 : ans) << '\n'; return 0; }