問題文

とある仮想空間ではマップにある武器を拾って戦うゲームがあります。

このゲームを $K$ 人のユーザーで遊ぶことになりました。このゲームはマップが $N$ 頂点 $M$ 辺の連結な単純無向グラフで構成されており、辺 $i$ は頂点 $U_i$ と $V_i$ を双方向で結んでおり、その間の距離は $D_i$ です。

ゲーム開始時ユーザー $i$ は 頂点 $A_i$ にいます。また、頂点 $i$ には $B_i$ 個の武器が落ちています。ユーザーは落ちている武器を一つまで拾うことができますが、誰かが拾ってしまった武器は拾えません。

開始時は全てのユーザーが武器を持っていないため全員が頂点間を移動をしながら武器を拾うところから始めます。（移動しなくても武器がある場合、そのまま拾う事ができます）

ここで武器の合計数は $K$ 以上あることが保証されています。全てのユーザーが武器を拾うまでの全員の移動距離の合計としてありうるものの最低値を求めてください。

入力

$K\ N\ M$
$A_1\ A_2\ \dots A_K$ 
$B_1\ B_2\ \dots B_N$ 
$U_1\ V_1\ D_1$
$U_2\ V_2\ D_2$
$\vdots$
$U_M\ V_M\ D_M$

• 入力は全て整数
• $1\le K \le 2000$
• $1\le N \le 2000$
• $N-1\le M \le \min \left( \frac{N(N-1)}{2},2000 \right)$
• $1\le A_i \le N$
• $0\le B_i \le K$
• $K \le \sum B_i$
• $1\le U_i,V_i \le N$
• $U_i \neq V_i$
• $1\le D_i \le 10^{12}$
• 与えられるグラフは単純かつ連結

出力

答えを出力せよ

サンプル

4 5 4
1 1 1 4
1 1 2 0 0
1 2 4
1 3 5
4 5 1
5 3 3

13

4 5 4
2 3 4 5
4 0 0 0 0
1 2 1
1 3 1
1 4 1
1 5 1

4

20 10 10
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
4 0 0 3 3 0 1 5 0 4
1 2 4
2 3 2
3 4 3
4 5 1
5 6 2
6 7 4
7 8 5
2 9 3
6 9 1
9 10 8

54