class UnionFind: def __init__(self, n): self.n = n self.parent = list(range(n)) self.rank = [0] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x == root_y: return False if self.rank[root_x] < self.rank[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x if self.rank[root_x] == self.rank[root_y]: self.rank[root_x] += 1 return True def same(self, x, y): return self.find(x) == self.find(y) 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 個以下 ワーシャルフロイドが回せるね # Wi = 0 とかいうゲキヤバケースみて笑ってる import sys input = lambda: sys.stdin.readline().rstrip() n, m, q = map(int, input().split()) s = [0] + list(map(int, input().split())) edges_input = [tuple(map(int, input().split())) for _ in range(m)] uf = UnionFind(n + 1) for u, v, w in edges_input: if w == 0: uf.union(u, v) s[uf.find(u)] = min(s[u], s[uf.find(u)]) s[uf.find(v)] = min(s[v], s[uf.find(v)]) edges = [] candidate = {0 : 0} for i in range(1, m + 1): u, v, w = edges_input[i - 1] u = uf.find(u) v = uf.find(v) if i <= 60 or w == 0: c = w * 2**i if c >= 2e18: continue 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 i in dist: # print(i) # print(candidate) for _ in range(q): a, b = map(int, input().split()) a = uf.find(a) b = uf.find(b) if a not in candidate and 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]])