#include <bits/stdc++.h>
//#include "atcoder/all"

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")

using namespace std;

using i64 = long long;


void solve(){
  int n, m, K;
  cin >> n >> m >> K;
  vector<i64> c(m);
  vector<vector<pair<int,i64>>> edges(n);
  for(int i = 0; i < m; ++i){
    cin >> c[i];
  }
  for(int i = 0; i < m; ++i){
    int a, b;
    cin >> a >> b;
    --a, --b;
    edges[a].emplace_back(b, c[i]);
    edges[b].emplace_back(a, c[i]);
  }
  vector<vector<i64>> dp(n, vector<i64>(K + 1, 1e18));
  priority_queue<tuple<i64, int, int>, vector<tuple<i64, int, int>>, greater<tuple<i64, int, int>>> pq;
  dp[0][0] = 0;
  pq.emplace(0, 0, 0);
  while(!pq.empty()){
    auto [d, v, k] = pq.top();
    pq.pop();
    if(dp[v][k] < d) continue;
    for(auto [u, w] : edges[v]){
      if(dp[u][k] > d + w){
        dp[u][k] = d + w;
        pq.emplace(dp[u][k], u, k);
      }
      if(k != K && dp[u][k + 1] > d){
        dp[u][k + 1] = d;
        pq.emplace(dp[u][k + 1], u, k + 1);
      }
    }
  }
  i64 ans = 1e18;
  for(int i = 0; i <= K; ++i){
    ans = min(ans, dp[n - 1][i]);
  }
  cout << (ans == 1e18 ? -1 : ans) << endl;
}

signed main(){
  solve();
}