F - 昂贵的旅费

分值：500分

问题描述

AtCoder 王国由 $N$ 个城镇和 $N-1$ 条道路组成。
城镇按照Town $1$, Town $2$, $\dots$, Town $N$进行编号。 同样，道路按照Road $1$, Road $2$, $\dots$, Road $N-1$进行编号。 第 $i$ 条道路双向连接 Towns $A_i$ 和 $B_i$，你需要支付过路费 $C_i$。 对于每对不同的城镇 $(i, j)$，可以通过道路从 Town $A_i$ 到 Town $B_j$。

给你一个序列 $D = (D_1, D_2, \dots, D_N)$，其中 $D_i$ 是在 Town $i$ 参观的成本。 让我们把从 Town $i$ 到 Town $j$ 的旅行费用 $E_{i,j}$ 定义为从 Town $i$ 到 Town $j$ 的全程费用之和，再加上 $D_{j}$。

• 更正式地，$E_{i,j}$ 是定义为 $D_j + \displaystyle\sum_{l=0}^{k-1} c_l$，其中从 $i$ 到 $j$ 的最短路径是 $i = p_0, p_1, \dots, p_{k-1}, p_k = j$，而连接 Towns $p_{l}$ 和 $p_{l+1}$ 的道路的过路费是 $c_l$。

对于每个 $i$，找出从 Town $i$ 到其他城镇的旅行费用的最大值。

• 更正式地，对于每个 $i$，找出 $ \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$，可以通过一些道路从 Town $i$ 到 Town $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}$。