import heapq
import math

INF = math.inf
n, m, k = map(int, input().split())
c = list(map(int, input().split()))
bridge = []
for i in range(m):
    u, v = map(int, input().split())
    bridge.append([u, v])


def dijkstra(
    start,
):  # 街1から街Nに最小の経費で向かいたい、K枚のクーポンを使うことができる
    dist = [[INF] * (k + 1) for _ in range(n + 1)]
    dist[start][0] = 0
    que = []
    heapq.heappush(que, (0, start, 0))  # (cost,now,クーポンの枚数)
    while que:
        cost, now, coupon = heapq.heappop(que)
        if dist[now][coupon] < cost:
            continue
        for i in range(m):
            u, v = bridge[i]
            if u == now:
                if dist[v][coupon] < cost + c[i]:
                    continue
                if coupon < k and dist[v][coupon + 1] > cost:
                    dist[v][coupon + 1] = cost
                    heapq.heappush(que, (cost, v, coupon + 1))
                if dist[v][coupon] > cost + c[i]:
                    dist[v][coupon] = cost + c[i]
                    heapq.heappush(que, (cost + c[i], v, coupon))
            elif v == now:
                if dist[u][coupon] < cost + c[i]:
                    continue
                if coupon < k and dist[u][coupon + 1] > cost:
                    dist[u][coupon + 1] = cost
                    heapq.heappush(que, (cost, u, coupon + 1))
                if dist[u][coupon] > cost + c[i]:
                    dist[u][coupon] = cost + c[i]
                    heapq.heappush(que, (cost + c[i], u, coupon))
    return dist[n][k]  # 街Nに到達するための最小の経費


ans = dijkstra(1)
if ans == INF:
    print(-1)
else:
    print(ans)