ztm 的肉鸽游戏

ztm 最近在玩一个 $roguelike$ 类型的游戏，这个游戏的每一关都有 $n$ 个地点，每个地点有对应的功能——"商店"，"普通怪物"，"精英怪物"，"随机事件" 等等

但是不论这个游戏如何设计，最终问题说白了就是让玩家从某个点出发，尝试获得最大收益

所以 ztm 将地图进行了化简，首先 ztm 将所有的游戏内数值（血量，魔法值，状态效果等等）全部转换成用金币来描述!

并且他挑出了 $n - 1$ 条路径来连接所有的地点，穿过每条路径，不论路径上是什么事件，均看作是需要花费一定的金币，到达某个地点时也不论是什么事件，均可以看作会收获一些金币

现在 ztm 想知道，他应该选择哪一个点作为起点，来获得最大收益？

为了方便 ztm 选择，请你计算出任意点作为起点时可以获得的最大收益

请注意，在游戏中是允许玩家重复经过某一条路径，也允许玩家重复到达某个地点，但是每次经过路径都需要花费对应的金币，而只有第一次到达某个地点时才会获得金币

输入第一行包含一个整数 $n$ 表示有 $n$ 个地点接下来 $n - 1$ 行，每行输入三个整数 $u,v,w$ 表示 $u,v$ 两个点之间存在一条双向路径，经过这条路径需要花费 $w$ 个金币最后一行包含 $n$ 个整数 $a_i$ ，分别表示第一次到达每个地点时能获得的金币

输出 $n$ 行，每行一个整数表示从第 $i$ 个点出发时能获得的最大金币数量

对于 $20\%$ 的数据，满足 $N \leq 10$

对于 $50\%$ 的数据，满足 $N \leq 1000$

对于 $100\%$ 的数据，满足 $1 \leq N \leq 3 * 10^5，1 \leq w,a_i \leq 10^5$ 。

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

#7203. ztm的肉鸽游戏