n,m,q = 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 = map(int, input().split()) u -= 1 v -= 1 if i < 61: cos = pow(2,(i+1))*w if cos <= 10**19: edge[u].append([v,cos]) edge[v].append([u,cos]) se.add(u) se.add(v) dic = {} from heapq import heappush, heappop def dijkstra(G, s): INF = 10**20 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) mi = 10**20 for j in se: dic[(i,j)] = dis[j] dis[j] += s[j] mi = min(mi,dis[j]) dic[i] = mi for _ in range(q): a,b = map(int, input().split()) a -= 1 b -= 1 ans = s[a]+s[b] if a in se: ans = min(ans,dic[a]+s[b]) if b in se: ans = min(ans,dic[a]+dic[b]) if b in se: ans = min(ans,dic[b]+s[a]) if (a,b) in dic: ans = min(ans,dic[(a,b)]) print(ans)