import heapq

n,m,k = map(int, input().split())
c = list(map(int, input().split()))
graph = [[] for _ in range(n)]

for i in range(m):
    u,v = map(int, input().split())
    graph[u-1].append((v-1, c[i]))
    graph[v-1].append((u-1, c[i]))

start = 0
end = n-1

dist = [[10**17] * (k + 1) for _ in range(n)]

dist[start][0] = 0

queue = [(0, start, 0)]

while queue:
    now_cost, now_pos, coupon = heapq.heappop(queue)

    if dist[now_pos][coupon] < now_cost:
        continue

    for to, edge_cost in graph[now_pos]:
        if coupon < k:
            if dist[to][coupon + 1] > now_cost:
                dist[to][coupon + 1] = now_cost
                heapq.heappush(queue, (now_cost, to, coupon + 1))

        if dist[to][coupon] > now_cost + edge_cost:
            dist[to][coupon] = now_cost + edge_cost
            heapq.heappush(queue, (now_cost + edge_cost, to, coupon))

ans = min(dist[end])

if ans == 10**17:
    print(-1)
else:
    print(ans)