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])] n,m,q = list(map(int, input().split())) 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 i<90 and (1<vals[u]: continue # order.append(u) for d,v in ns[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) da = dijkstra(a,ns) db = dijkstra(b,ns) ba = bb = INF for u,val in da.items(): ba = min(ba, val+s[u]) for u,val in db.items(): bb = min(bb, val+s[u]) res = ba+bb if b in da: res = min(res, da[b]) print(res)