E: ジャム (Jam)

問題

ある国には N 個の街があり、1,\ 2,\ ...,\ N の番号がつけられています。これらの街は M 本の道で双方向に結ばれており、i 番目の道を使うと街 u_i と v_i の間を時間 t_i で移動することができます。また、どの 2 つの街もいくつかの道を使うことで行き来することができます。

それぞれの街では食パンが売られており、街 i で売られている食パンの美味しさは P_i です。

さらに、この国には K 種類の味のジャムがあり、街 i では味 c_i で美味しさ J_i のジャムを買うことができます。

街 1 に住んでいるほむちゃんは、これからパンとジャムを 1 つずつ買いにお出かけすることにしました。ほむちゃんは、いくつかの街を移動してパンとジャムを買って街 1 に戻ってきます。より正確には、ある街 u に移動してパンを買い、ある街 v を選んでジャムを買い、街 1 に戻ってきます。この際、u=v や u=1 、v=1 でも構いません。

お買い物を終えたほむちゃんの幸福度は、「買ったパンとジャムの美味しさの合計」ー「移動にかかった時間」です。K 種類それぞれのジャムについて、その味のジャムとパンを買いに行くときの幸福度として考えられる最大値を計算してください。

入力形式

N M K
P_1 P_2 ... P_N
c_1 c_2 ... c_N
J_1 J_2 ... J_N
u_1 v_1 t_1
u_2 v_2 t_2
:
u_M v_M t_M

制約

出力形式

K 行出力してください。i 行目にはパンと味 i のジャムを買いに行く場合の幸福度の最大値を出力してください。

入力例 1

4 4 3
3 6 1 6
1 1 2 3
6 1 5 5
1 2 1
2 3 1
1 3 1
1 4 1

出力例 1

10
8
9

入力例 2

2 1 2
1 1
1 2
1 1
1 2 1000000000

出力例 2

2
-1999999998

入力例 3

6 8 3
31 41 59 26 53 58
1 2 3 1 2 3
27 18 28 18 28 46
1 2 3
2 3 7
2 4 8
3 6 9
3 5 3
4 5 3
1 5 15
4 6 7

出力例 3

66
61
68