from heapq import heappop as pop, heappush as push N, M, K = map(int, input().split()) C = list(map(int, input().split())) uv = [map(int, input().split()) for _ in range(M)] edges = [[] for _ in range(N*4)] for c, (u, v) in zip(C, uv): u -= 1 v -= 1 for i in range(K+1): edges[i*N+u].append((i*N+v, c)) edges[i*N+v].append((i*N+u, c)) if i: edges[(i-1)*N+u].append((i*N+v, 0)) edges[(i-1)*N+v].append((i*N+u, 0)) dist = [float("inf")]*(N*(K+1)) pq = [(0, 0)] dist[0] = 0 while pq: c, v = pop(pq) if dist[v] < c: continue if v%N == N-1: print(c) break for u, bc in edges[v]: if dist[u] <= c + bc: continue dist[u] = c+bc push(pq, (c+bc, u)) else: print(-1)