### 问题描述 捡到一张寻宝图，寻宝图是一棵由 $N$ 个节点组成的树，寻宝者到达每个点都会获得这个点上的宝藏，每个宝藏都有一定的价值，但是经过每条边也要支付一定的过路费。虽然每个点只有一个宝藏，但是过路费只要走过都要交。雨可不想盲目地去当冤大头，她想快速地计算出从每个点出发能获得的最大收益，请你帮她计算这个值。 ### 输入格式 第一行为一个正整数 $N$ 。接下来 $N-1$ 行，每行三个整数，描述一条双向边的两个端点 $x, y$ 和过路费 $z$ 。 最后一行 $N$ 个数，表示每个点上宝藏的价值 $a_i$ 。 ### 输出格式 输出 $N$ 行，每行一个数。第 $i$ 行表示从 $i$ 出发的最大收益。 ### 样例输入 ```text 6 1 2 1 2 3 3 3 4 36 3 6 13 3 5 2 6 8 9 10 13 1 ``` ### 样例输出 ```text 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$ 。