题目描述

有一颗 $n$ 个点，$n - 1$ 条边带边权的树，现在定义从点 $i$ 到点 $j$ 的距离是点 $i$ 走到点 $j$ 路上的边权和加上 $d_j$，问每个点到其它点的最长距离，要求 $i\not =j$。

输入格式

第一行输入一个整数 $n$

接下来 $n-1$ 行每行三个整数代表 $u,v,w$

最后一行输入 $n$ 个整数代表每个点的点权 $d_i$

输出格式

输出一共输出 $n$ 行，每行一个整数代表离 $i$ 最远的距离。

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)$