from heapq import heappop, heappush
INF = float("inf")

def dijkstra(graph, n, s):
    d = [INF] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist, v = heappop(q)
        if d[v] < dist: continue
        for nv, cost in graph[v]:
            if d[nv] > d[v] + cost:
                d[nv] = d[v] + cost
                heappush(q, (d[nv], nv))
    return d

n, m, k = map(int, input().split())
c = list(map(int, input().split()))
g = [[] for _ in range(n*4+10)]
for i in range(m):
    u, v = map(lambda x: int(x)-1, input().split())
    for j in range(k+1):
        g[n*j+u].append((n*j+v, c[i]))
        g[n*j+v].append((n*j+u, c[i]))
    for j in range(k):
        g[n*j+u].append((n*(j+1)+v, 0))
        g[n*j+v].append((n*(j+1)+u, 0))

res = dijkstra(g, n*4+10, 0)
ans = min(res[n*j+n-1] for j in range(k+1))
print(ans if ans != INF else -1)