import sys import heapq def dijkstra(start, graph, INF): n = len(graph) dist = [INF] * n dist[start] = 0 hq = [(0, start)] while hq: d, now = heapq.heappop(hq) if dist[now] < d: continue for nxt, cost in graph[now]: if dist[nxt] > d + cost: dist[nxt] = d + cost heapq.heappush(hq, (dist[nxt], nxt)) return dist def main(): input = sys.stdin.readline n, m, k = map(int, input().split()) c = list(map(int, input().split())) graph = [[] for _ in range(n * (k + 1))] for i in range(m): u, v = map(int, input().split()) u -= 1 v -= 1 for j in range(k + 1): graph[n * j + u].append((n * j + v, c[i])) graph[n * j + v].append((n * j + u, c[i])) if j != k: graph[n * j + u].append((n * (j + 1) + v, 0)) graph[n * j + v].append((n * (j + 1) + u, 0)) INF = 2 * 10**18 dist = dijkstra(0, graph, INF) ans = INF for j in range(k + 1): ans = min(ans, dist[n * j + (n - 1)]) print(-1 if ans == INF else ans) main()