题目描述

蒙自一中王国由 $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}$ 定义为：从城市 $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。
接下来N-1行，每行三个数ABC分别代表起点终点和费用
最后一行n个数，表示费用$D_i$

输出格式

输出 $N$ 行。第 $i$ 行输出 $\max_{1 \leq j \leq N,\, j \neq i} E_{i,j}$。

3
1 2 2
2 3 3
1 2 3

8
6
6

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 \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)$
• 对于任意满足 $1 \leq i < j \leq N$ 的整数对 $(i, j)$，都可以通过若干道路从城市 $i$ 到城市 $j$。
• 所有输入均为整数。

样例解释 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$