该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

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

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

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

输入格式

输入第一行包含一个整数 $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

样例输出

30 
29 
28 
10 
30 
16