n,m,q = map(int, input().split()) s = list(map(int, input().split())) edge = [[] for _ in range(n)] ee = [] se = set() from atcoder.dsu import DSU uf = DSU(n) lead = list(range(n)) 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: ee.append([u,v,cos]) else: if w == 0: uf.merge(u,v) for i in range(n): lead[i] = uf.leader(i) for u,v,cos in ee: lu,lv = lead[u],lead[v] edge[lu].append([lv,cos]) edge[lv].append([lu,cos]) se.add(lu) se.add(lv) 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 a = lead[a] b = lead[b] ans = s[a]+s[b] if a == b: ans = 0 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)