#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 1e15;

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<ll> c(m);
  for (int i = 0; i < m; i++) {
    cin >> c[i];
  }
  vector g(n, vector<pair<ll, int>>(n));
  for(int i=0; i<m; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    g[u].push_back({c[i], v});
    g[v].push_back({c[i], u});
  }

  vector dist(n, vector<ll>(k+1, INF));
  dist[0] = {0, 0};
  priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
  pq.push({0, {0, 0}});
  while (!pq.empty()) {
    auto [d, qv] = pq.top();
    auto [q, v] = qv;
    pq.pop();
    if (dist[v][q] < d) continue;
    for(auto [cost, nxt] : g[v]) {
      if(dist[nxt][q] > d + cost) {
        dist[nxt][q] = d + cost;
        pq.push({dist[nxt][q], {q, nxt}});
      }
      if(q < k && dist[nxt][q+1] > d) {
        dist[nxt][q+1] = d;
        pq.push({dist[nxt][q+1], {q+1, nxt}});
      }
    }
  }
  ll ans = INF;
  for(int i=0; i<=k; i++) {
    ans = min(ans, dist[n-1][i]);
  }
  if(ans == INF) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }

}