import heapq from collections import defaultdict N,M,Q = list(map(int,input().split())) S = list(map(int,input().split())) edge = [[] for _ in range(N)] for i in range(M): u,v,w = list(map(int,input().split())) u -= 1;v -= 1 if(w == 0): edge[u].append((v, 0)) edge[v].append((u, 0)) else: if(i > 63):continue if(w * (1<<(i+1)) > 2*10**18):continue edge[u].append((v, w * (1<<(i+1)))) edge[v].append((u, w * (1<<(i+1)))) INF = 3*10**18 dist_from_warp = [INF] * N q = [(S[i], i) for i in range(N)] heapq.heapify(q) while(q): v,now = heapq.heappop(q) if(dist_from_warp[now] <= v):continue dist_from_warp[now] = v for i,w in edge[now]: heapq.heappush(q, (v + w, i)) for _ in range(Q): a,b = list(map(int,input().split())) a -= 1;b -= 1 ans = dist_from_warp[a] + dist_from_warp[b] q = [(0,a)] dist = defaultdict(lambda:INF) while(q): v,now = heapq.heappop(q) if(now == b): ans = min(ans, v) break if(dist[now] <= v):continue dist[now] = v for i,w in edge[now]: heapq.heappush(q, (v+w, i)) print(ans)