You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[丛雨]捡到一张寻宝图，寻宝图是一棵由 $N$ 个节点组成的树，寻宝者到达每个点都会获得这个点上的宝藏，每个宝藏都有一定的价值，但是经过每条边也要支付一定的过路费。虽然每个点只有一个宝藏，但是过路费只要走过都要交。丛雨可不想盲目地去当冤大头，她想快速地计算出从每个点出发能获得的最大收益，请你帮她计算这个值。

输入格式（trea.in）

第一行为一个正整数 $N$ 。接下来 $N-1$ 行，每行三个整数，描述一条双向边的两个端点 $x, y$ 和过路费 $z$ 。 最后一行 $N$ 个数，表示每个点上宝藏的价值 $a_i$ 。

输出格式（trea.out）

输出 $N$ 行，每行一个数。第 $i$ 行表示从 $i$ 出发的最大收益。

输入样例

6 
1 2 1 
2 3 3 
3 4 36 
3 6 13 
3 5 2 
6 8 9 10 13 1

输出样例

30 
29 
28 
10 
30 
16

数据范围

对于 $20\%$ 的数据，满足 $N \le 10$ 。 对于 $50\%$ 的数据，满足 $N \le 1000$ 。 对于 $100\%$ 的数据，满足 $1 \le N \le 3*10^5, 1 \le z, a_i \le 10^5$ 。