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())) # 最小費用流 # まず、グラフ作り V=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) for i in range(N): add_edge(i,goal,B[i],0) for i in range(M): u,v,d=map(int,input().split()) u-=1 v-=1 add_edge(u,v,1<<61,d) add_edge(v,u,1<<61,d) #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)