import heapq

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    C = list(map(int, data[3:3 + M]))
    uv = data[3 + M:]
    
    graph = [[] for _ in range(N+1)]
    for i in range(M):
        u = int(uv[2*i])
        v = int(uv[2*i+1])
        cost = C[i]
        graph[u].append((v, cost))
        graph[v].append((u, cost))

    # dist[町][使用済みクーポン数] = 最小コスト
    INF = 10**18
    dist = [[INF] * (K+1) for _ in range(N+1)]
    dist[1][0] = 0
    hq = []
    heapq.heappush(hq, (0, 1, 0))  # (今のコスト, 町, 使ったクーポン枚数)

    while hq:
        cost, u, used = heapq.heappop(hq)
        if dist[u][used] < cost:
            continue
        for v, edge_cost in graph[u]:
            # クーポンを使わない
            if dist[v][used] > cost + edge_cost:
                dist[v][used] = cost + edge_cost
                heapq.heappush(hq, (dist[v][used], v, used))
            # クーポンを使う
            if used < K and dist[v][used+1] > cost:
                dist[v][used+1] = cost
                heapq.heappush(hq, (dist[v][used+1], v, used+1))
    
    ans = min(dist[N])
    print(ans if ans < INF else -1)

if __name__ == "__main__":
    solve()