昂贵的开销

题目描述

AtCoder 王国由 $N$ 个城镇和 $N-1$ 条道路组成。

城镇被编号为 Town $1$、Town $2$、$\dots$、Town $N$。 同样地，道路被编号为 Road $1$、Road $2$、$\dots$、Road $N-1$。 道路 $i$ 双向连接城镇 $A_i$ 和城镇 $B_i$，通过它需要支付过路费 $C_i$。任意一对不同的城镇 $(i, j)$ 之间都可以通过道路互相到达。

给定一个数列 $D = (D_1, D_2, \dots, D_N)$，其中 $D_i$ 是在城镇 $i$ 观光所需的费用。

定义从城镇 $i$ 到城镇 $j$ 的旅行费用 $E_{i,j}$ 为：从城镇 $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$，求 $\displaystyle \max_{1 \le j \le 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 \le j \le N, j \neq i} E_{i,j}$。

样例

3
1 2 2
2 3 3
1 2 3

8
6
6

对于每一对城镇 $(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$

6
1 2 3
1 3 1
1 4 4
1 5 1
1 6 5
9 2 6 5 3 100

105
108
106
109
106
14

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

5000000006
4000000006
3000000006
3000000001
4000000001
5000000001

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$ $(1 \le i \le N-1)$
• $1 \le B_i \le N$ $(1 \le i \le N-1)$
• $1 \le C_i \le 10^9$ $(1 \le i \le N-1)$
• $1 \le D_i \le 10^9$ $(1 \le i \le N)$
• 对于满足 $1 \le i \lt j \le N$ 的整数对 $(i,j)$，可以通过若干条道路从城镇 $i$ 到达城镇 $j$。
• 输入中的所有值均为整数。