#include using namespace std; using std::cin; using std::cout; #define rep(i,n) for(int i = 0; i < (int)n; i++) #define FOR(n) for(int i = 0; i < (int)n; i++) #define repi(i,a,b) for(int i = (int)a; i < (int)b; i++) #define all(x) x.begin(),x.end() //#define mp make_pair #define vi vector #define vvi vector #define vvvi vector #define vvvvi vector #define pii pair #define vpii vector> template bool chmax(T &a, const T b) {if(a bool chmin(T &a, const T b) {if(a>b) {a=b; return true;} else {return false;}} using ll = long long; using ld = long double; using ull = unsigned long long; const ll INF = numeric_limits::max() / 2; const ld pi = 3.1415926535897932384626433832795028; const ll mod = 998244353; int dx[] = {1, 0, -1, 0, -1, -1, 1, 1}; int dy[] = {0, 1, 0, -1, -1, 1, -1, 1}; #define int long long vector dijkstra(vector>> &graph, int start) { int n = (int)graph.size(); priority_queue, vector>, greater>> pq; vector dist(n, INF); dist[start] = 0; pq.emplace(dist[start], start); while(!pq.empty()) { pair p = pq.top(); pq.pop(); int v = p.second; if(dist[v] < p.first) continue; for(auto e : graph[v]) { if(dist[e.first] > dist[v] + e.second) { dist[e.first] = dist[v] + e.second; pq.emplace(dist[e.first], e.first); } } } return dist; } void solve() { int n, m, k; cin >> n >> m >> k; vi c(m); FOR(m) cin >> c[i]; vector g(n * (k + 1)); FOR(m) { int u, v; cin >> u >> v; --u; --v; rep(j, k + 1) { g[u + j*n].emplace_back(v + j*n, c[i]); g[v + j*n].emplace_back(u + j*n, c[i]); if (j != k) { g[u + j*n].emplace_back(v + (j+1)*n, 0); g[v + j*n].emplace_back(u + (j+1)*n, 0); } } } vi dist = dijkstra(g, 0); int ans = INF; rep(i, k+1) chmin(ans, dist[n - 1 + i * n]); cout << (ans == INF? -1 : ans) << endl; } signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }