# 誤解法6: C++ で `long long c = W * (1LL << i);` がオーバーフローする実装を模倣(i<=62 で計算し、0<=c<=2e18 なら採用) # - 答え <= S_a + S_b <= 2e18 なので、コスト > 2e18 の辺は不要(W>=1 かつ i>=61 は全部不要) # - W=0 の辺は Union-Find で縮約 # - 残る辺は高々 60 本 → 縮約後の頂点 120 個以下で Floyd–Warshall # - ワープは高々 1 回で十分。f(v) = min_x (d(v,x) + S_x) として ans = min(d(a,b), f(a)+f(b)) import sys def solve(inp): d = inp.split(); p = 0 N, M, Q = int(d[0]), int(d[1]), int(d[2]); p = 3 S = [int(x) for x in d[p:p+N]]; p += N LIMIT = 2 * 10**18 INF = float('inf') par = list(range(N)) def find(x): while par[x] != x: par[x] = par[par[x]]; x = par[x] return x small = [] for i in range(1, M+1): u, v, w = int(d[p])-1, int(d[p+1])-1, int(d[p+2]); p += 3 if w == 0: a, b = find(u), find(v) if a != b: par[a] = b elif i <= 62: c = (w << i) & ((1 << 64) - 1) if c >= 1 << 63: c -= 1 << 64 if 0 <= c <= LIMIT: small.append((u, v, c)) minS = {} for v in range(N): r = find(v) minS[r] = min(minS.get(r, S[v]), S[v]) idx = {} es = [] for u, v, c in small: ru, rv = find(u), find(v) if ru == rv: continue for r in (ru, rv): if r not in idx: idx[r] = len(idx) es.append((idx[ru], idx[rv], c)) K = len(idx) D = [[INF]*K for _ in range(K)] for k in range(K): D[k][k] = 0 for a, b, c in es: if c < D[a][b]: D[a][b] = D[b][a] = c for k in range(K): Dk = D[k] for i in range(K): dik = D[i][k] if dik == INF: continue Di = D[i] for j in range(K): if dik + Dk[j] < Di[j]: Di[j] = dik + Dk[j] rev = [None]*K for r, k in idx.items(): rev[k] = r f = dict(minS) for k in range(K): f[rev[k]] = min(D[k][j] + minS[rev[j]] for j in range(K)) out = [] for _ in range(Q): a, b = int(d[p])-1, int(d[p+1])-1; p += 2 ra, rb = find(a), find(b) if ra == rb: out.append(0); continue dd = D[idx[ra]][idx[rb]] if ra in idx and rb in idx else INF out.append(min(dd, f[ra] + f[rb])) return "\n".join(map(str, out)) + "\n" if __name__ == "__main__": sys.stdout.write(solve(sys.stdin.read()))