import sys, random input = lambda : sys.stdin.readline().rstrip() write = lambda x: sys.stdout.write(x+"\n"); writef = lambda x: print("{:.12f}".format(x)) debug = lambda x: sys.stderr.write(x+"\n") YES="Yes"; NO="No"; pans = lambda v: print(YES if v else NO); LI = lambda v=0: list(map(lambda i: int(i)-v, input().split())); II=lambda : int(input()); SI=lambda c0: [ord(c)-ord(c0) for c in input()] def debug(_l_): for s in _l_.split(): print(f"{s}={eval(s)}", end=" ") print() def dlist(*l, fill=0): if len(l)==1: return [fill]*l[0] ll = l[1:] return [dlist(*ll, fill=fill) for _ in range(l[0])] class UF: # unionfind def __init__(self, n): self.n = n self.parent = list(range(n)) self.size = [1] * n # self.es = [0] * n def check(self): return [self.root(i) for i in range(self.n)] def root(self, i): inter = set() while self.parent[i]!=i: inter.add(i) i = self.parent[i] r = i for i in inter: self.parent[i] = r return r def merge(self, i, j): # 繋いだかどうかを返す ri = self.root(i) rj = self.root(j) if ri==rj: # self.es[ri] += 1 return False if self.size[ri]>self.size[rj]: ri,rj = rj,ri self.parent[ri] = rj self.size[rj] += self.size[ri] # self.es[rj] += self.es[ri] + 1 return True def rs(self): return sorted(set([self.root(i) for i in range(self.n)])) def groups(self): gs = {} for u in range(self.n): gs.setdefault(self.root(u), []).append(u) for item in gs.values(): item.sort() return gs n,m,q = list(map(int, input().split())) uf = UF(n) s = LI() ns = [[] for _ in range(n)] INF = 7*(10**18) for i in range(1,m+1): u,v,w = LI() u -= 1 v -= 1 if w==0: uf.merge(u,v) continue if i<90 and (1<vals[u]: continue # order.append(u) for d,v in ns.get(u, []): if v not in vals or vals[v]>val+d: vals[v] = val+d hp(h, to(vals[v], v)) return vals #, order for i in range(q): a,b = LI(1) ra = uf.root(a) rb = uf.root(b) da = dijkstra(ra,nns) db = dijkstra(rb,nns) ba = bb = INF for ru,val in da.items(): ba = min(ba, val+ss[ru]) for ru,val in db.items(): bb = min(bb, val+ss[ru]) res = ba+bb if rb in da: res = min(res, da[rb]) print(res)