#pragma GCC optimize("O3") #include #include using namespace std; typedef long long ll; const int INF = 1<<30; const ll INFLL = 1LL<<60; const ll MOD = 1000000007; const double INFD = 1.0E10; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, -1, 0, 1}; //const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1}; //const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; using Pair = pair; using Graph = vector >; using mint = atcoder::modint1000000007; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); int n, m, k; cin >> n >> m >> k; vector C(m); for (int i = 0; i < m; i++) cin >> C[i]; vector>> G(n); for (int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--; v--; G[u].push_back({v, C[i]}); G[v].push_back({u, C[i]}); } vector> dp(n, vector(k + 1, INFLL)); using Pair = tuple; priority_queue, greater> pq; pq.push({0, 0, 0}); while (!pq.empty()){ auto [d, v, cnt] = pq.top(); pq.pop(); //cerr << d << ' ' << v << ' ' << cnt << endl; if (dp[v][cnt] < INFLL) continue; dp[v][cnt] = d; for (auto [nv, w] : G[v]){ for (int i = 0; i < 2; i++){ if (cnt + i > k) continue; if (dp[nv][cnt + i] < INFLL) continue; pq.push({d + (i == 0 ? w : 0), nv, cnt + i}); } } } ll ans = INFLL; for (int i = 0; i <= k; i++) ans = min(ans, dp[n - 1][i]); cout << (ans < INFLL ? ans : -1) << endl; return 0; }