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

制約

• 1\leq N\leq 10^5
• 1\leq M\leq 2\times 10^5
• 1\leq K\leq N
• 1\leq P_i, J_i\leq 10^9
• 1\leq c_i\leq K
• 1\leq u_i, v_i \leq N
• 1\leq t_i \leq 10^9
• すべての i\ (1\leq i\leq K) について、c_j=i となるj\ (1\leq j\leq N) が存在する
• 与えられるグラフは多重辺や自己ループを含まない連結なグラフである
• 入力はすべて整数で与えられる

出力形式

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

• 味 1 のジャムを買う場合
• 街 1 でジャムを買い、街 2 に移動してパンを買い、街 1 に戻ってくると、幸福度は 6+6-2=10 となりこれが最適です。
• 味 2 のジャムを買う場合
• 街 2 に移動してパンを買い、街 3 に移動してジャムを買い、街 1 に戻ってくると、幸福度は 6+5-3=8 となります。
• 味 3 のジャムを買う場合
• 街 4 に移動してパンとジャムの両方を買って街 1 に戻ってくると、幸福度は 6+5-2=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

---