def warshall_floyd(n, edges, inf=float("inf")): assert n >= 0 dist = [[inf] * n for _ in range(n)] for v in range(n): dist[v][v] = 0 for u, v, w in edges: assert 0 <= u < n and 0 <= v < n if w < dist[u][v]: dist[u][v] = w for k in range(n): dk = dist[k] for i in range(n): dik = dist[i][k] if dik == inf: continue di = dist[i] for j in range(n): dkj = dk[j] if dkj == inf: continue nd = dik + dkj if nd < di[j]: di[j] = nd return dist # log(2)2e18 < 61 # 61 <= i 以降の辺は絶対いらない 誤読? # 頂点0=ワープ空間 # i <= 60 の辺で考慮する頂点は 120 個以下 ワーシャルフロイドが回せるね import sys input = lambda: sys.stdin.readline().rstrip() n, m, q = map(int, input().split()) s = [0] + list(map(int, input().split())) edges = [] candidate = {0 : 0} for i in range(1, m + 1): u, v, w = map(int, input().split()) if i <= 60: c = w * 2**i edges.append((u, v, c)) edges.append((v, u, c)) if u not in candidate: candidate[u] = len(candidate) if v not in candidate: candidate[v] = len(candidate) for u in candidate: if u == 0: continue edges.append((u, 0, s[u])) edges.append((0, u, s[u])) # print(edges) dist = warshall_floyd(len(candidate), [(candidate[u], candidate[v], w) for u, v, w in edges]) for _ in range(q): a, b = map(int, input().split()) if a not in candidate or b not in candidate: print(s[a] + s[b]) elif a in candidate and b not in candidate: print(dist[candidate[a]][0] + s[b]) elif a not in candidate and b in candidate: print(s[a] + dist[0][candidate[b]]) else: print(dist[candidate[a]][candidate[b]])