# 愚直解: 辺コストを多倍長で正確に計算し、ワープを完全グラフの辺として Dijkstra import sys, heapq 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 g = [[] for _ in range(N)] 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 c = w << i g[u].append((v, c)); g[v].append((u, c)) out = [] for _ in range(Q): a, b = int(d[p])-1, int(d[p+1])-1; p += 2 dist = [None]*N; dist[a] = 0; pq = [(0, a)] while pq: du, u = heapq.heappop(pq) if du != dist[u]: continue nb = list(g[u]) + [(x, S[u]+S[x]) for x in range(N) if x != u] for v, c in nb: nd = du + c if dist[v] is None or nd < dist[v]: dist[v] = nd; heapq.heappush(pq, (nd, v)) out.append(dist[b]) return "\n".join(map(str, out)) + "\n" if __name__ == "__main__": sys.stdout.write(solve(sys.stdin.read()))