问题陈述

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}$。

示例输入 1

3
1 2 2
2 3 3
1 2 3

示例输出 1

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$

示例输入 2

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

示例输出 2

105
108
106
109
106
14

示例输入 3

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

示例输出 3

5000000006
4000000006
3000000006
3000000001
4000000001
5000000001