n,m,q = list(map(int, input().split())) s = list(map(int, input().split())) edge = [[] for _ in range(n)] se = set() for i in range(m): u,v,w = list(map(int, input().split())) u -= 1 v -= 1 if i < 61: cos = pow(2,(i+1)) if cos <= (4*10**18)//w: edge[u].append([v,cos*w]) edge[v].append([u,cos*w]) se.add(u) se.add(v) dic = {} from heapq import heappush, heappop def dijkstra(G, s): INF = 4*10**18 dist = [INF] * len(G) dist[s] = 0 pq = [(0, s)] while pq: d, v = heappop(pq) if d > dist[v]: continue for u, weight in G[v]: nd = d + weight if dist[u] > nd: dist[u] = nd heappush(pq, (nd, u)) return dist for i in se: dis = dijkstra(edge,i) for j in se: dic[(i,j)] = dis[j] for j in range(n): dis[j] += s[j] dic[(i,-1)] = min(dis) for _ in range(q): a,b = list(map(int, input().split())) a -= 1 b -= 1 ans = s[a]+s[b] if a in se: ans = min(ans,dic[(a,-1)]+s[b]) if b in se: ans = min(ans,dic[(a,-1)]+dic[(b,-1)]) if b in se: ans = min(ans,dic[(b,-1)]+s[a]) if (a,b) in dic: ans = min(ans,dic[(a,b)]) print(ans)