AT_abc222_f [ABC222F] Expensive Expense

[problemUrl]: https://atcoder.jp/contests/abc222/tasks/abc222_f AtCoder 王国は $ N $ 個の街と $ N-1 $ 個の道路からなります。 街には 街 $ 1 $, 街 $ 2 $, $ \dots $, 街 $ N $ と番号がついています。道路にも同様に 道路 $ 1 $, 道路 $ 2 $, $ \dots $, 道路 $ N-1 $ と番号が付いています。 道路 $ i $ は街 $ A_i $ と $ B_i $ を双方向に結んでいて、通過するときに $ C_i $ の通行料がかかります。すべての異なる街の組 $ (i,\ j) $ に対して、道路を経由して街 $ i $ から街 $ j $ に行くことができます。 今、列 $ D\ =\ (D_1,\ D_2,\ \dots,\ D_N) $ が与えられます。 $ D_i $ は街 $ i $ を観光するときにかかる費用です。 このとき、街 $ i $ から街 $ j $ への旅費 $ E_{i,j} $ を、(同じ道を $ 2 $ 回以上使わずに街 $ i $ から街 $ j $ へ向かうときにかかる通行料の和) に $ D_{j} $ を足したものとして定めます。 - 厳密に言い換えると、$ i\ -\ j $ 間の最短パスを $ i\ =\ p_0,\ p_1,\ \dots,\ p_{k-1},\ p_k\ =\ j $ として、街 $ p_{l} $ と街 $ p_{l+1} $ を結ぶ道路の通行料を $ c_l $ と置いたときに $ E_{i,j}\ =\ D_j\ +\ \displaystyle\sum_{l=0}^{k-1}\ c_l $ と定義します。 すべての $ i $ に対して、街 $ i $ を始点として他の街へ旅行したときにありえる旅費の最大値を求めてください。 - 厳密に言い換えると、すべての $ i $ に対して $ \max_{1\ \leq\ j\ \leq\ N,\ j\ \neq\ i}\ E_{i,j} $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $ $ D_1 $ $ D_2 $ $ \dots $ $ D_N $

$ N $ 行出力せよ。$ i $ 行目には $ \displaystyle\ \max_{1\ \leq\ j\ \leq\ N,\ j\ \neq\ i}\ E_{i,j} $ を出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ N-1) $ - $ 1\ \leq\ B_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ N-1) $ - $ 1\ \leq\ C_i\ \leq\ 10^9 $ $ (1\ \leq\ i\ \leq\ N-1) $ - $ 1\ \leq\ D_i\ \leq\ 10^9 $ $ (1\ \leq\ i\ \leq\ N) $ - 整数の組 $ (i,j) $ が $ 1\ \leq\ i\ \lt\ j\ \leq\ N $ を満たすならば、街 $ i $ から街 $ j $ へいくつかの道路を通ることで移動できる。 - 入力はすべて整数である。 ### Sample Explanation 1 すべての街の順序つき組 $ (i,j) $ に対して $ E_{i,j} $ を計算すると次のようになります。 - $ E_{1,2}\ =\ 2\ +\ 2\ =\ 4 $ - $ E_{1,3}\ =\ 5\ +\ 3\ =\ 8 $ - $ E_{2,1}\ =\ 2\ +\ 1\ =\ 3 $ - $ E_{2,3}\ =\ 3\ +\ 3\ =\ 6 $ - $ E_{3,1}\ =\ 5\ +\ 1\ =\ 6 $ - $ E_{3,2}\ =\ 3\ +\ 2\ =\ 5 $