import sys import io, os input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline from heapq import heappop,heappush K,N,M=map(int,input().split()) A=list(map(int,input().split())) B=list(map(int,input().split())) E=[[] for i in range(N)] for i in range(M): u,v,d=map(int,input().split()) u-=1 v-=1 E[u].append((v,d)) E[v].append((u,d)) def dijkestra(fr): Q=[(0,fr)] DIS=[1<<61]*N DIS[fr]=0 while Q: dis,now=heappop(Q) if DIS[now]!=dis: continue for to,cost in E[now]: if DIS[to]>dis+cost: DIS[to]=dis+cost heappush(Q,(DIS[to],to)) return DIS # 最小費用流 # まず、グラフ作り V=N+N+2 # 頂点数 EDGE=[[] for i in range(V+1)] def add_edge(u,v,k,c): # u→vに容量k, 費用cの辺を張る X=[v,c,k,[]] Y=X[3]=[u,-c,0,X] EDGE[u].append(X) EDGE[v].append(Y) start=V-2 goal=V-1 C=[0]*N for a in A: C[a-1]+=1 for i in range(N): if C[i]==0: continue add_edge(start,i,C[i],0) DIS=dijkestra(i) for j in range(N): add_edge(i,N+j,K,DIS[j]) for i in range(N): add_edge(N+i,goal,B[i],0) #print(EDGE) Flowed_edge=[[] for i in range(V)] BACK=[-1]*(V) P=[0]*(V) # ポテンシャル LA=0 # 最終的な答え for fl in range(K): ANS=[1<<62]*V Q=[start] # 一次元化している。(time<<20)+node ANS[start]=0 while Q: # ここはダイクストラ x = heappop(Q) time = x>>20 fr = x - (time<<20) if time > ANS[fr]: continue for to,cost,vol,f_edge in EDGE[fr]: if vol>0 and ANS[to]>ANS[fr]+cost+P[fr]-P[to]:# ポテンシャルによりコストを調整 ANS[to]=ANS[fr]+cost+P[fr]-P[to] BACK[to]=fr Flowed_edge[to]=f_edge heappush(Q,((ANS[to])<<20)+to) LA+=ANS[goal]+P[goal] P=[P[i]+ANS[i] for i in range(V)] # ポテンシャルを調整 NOW=goal while NOW!=start: f_edge=Flowed_edge[NOW] f_edge[3][2]-=1 # 流した分の容量を削る f_edge[2]+=1 # 逆向きに+1する NOW=BACK[NOW] print(LA)