所有枯燥的树状土地都是相似的，而所有令人兴奋的树状土地则各有各的精彩。让 Treeland 比其他树状土地更令人兴奋的原因是当地最棒的电台主持人：Root 和 Leaf。每天早上在 FM 32.33（当然是循环播放），《全深度早间秀》（The Full Depth Morning Show）的 Root 和 Leaf 都会播报最热门的名人八卦和交通更新。

Treeland 地区由 $n$ 个城市组成，通过 $n - 1$ 条道路连接，使得每两个城市之间恰好有一条简单路径。第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，通行费为 $w_i$。

为了奖励忠实的听众，《全深度早间秀》正在赠送一些旅行套餐！Root 和 Leaf 将从寄给他们最多粉丝邮件的城市中选出 $n - 1$ 名幸运居民。这些居民中的每一位都会获得一张前往 Treeland 中不同城市的独特票据。

Treeland 的每个城市都有自己的奖品税：$t_i$。设 $d_{u,v}$ 为城市 $u$ 到 $v$ 的唯一简单路径上所有道路的通行费之和。对于从城市 $u$ 到城市 $v$ 的旅行，其旅行成本为 $(t_u + t_v)d_{u,v}$。

图 A.1：对应第一个样例输入的 Treeland 地图。

这些电台主持人还没有完全考虑清楚他们的奖品价值几何。他们需要向电台高管准备一份报告，以汇总预期的成本。对于每一个可能赢得奖品的城市，购买所有票据的总成本是多少？

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)。下一行包含 $n$ 个空格分隔的整数 $t_i$ ($1 \le t_i \le 1\,000$)，表示每个城市的税费。接下来的 $n - 1$ 行，每行包含 3 个整数 $u_i, v_i, w_i$，表示第 $i$ 条道路连接城市 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，通行费为 $w_i$ ($1 \le w_i \le 1\,000$)。

输出格式

输出 $n$ 行。第 $i$ 行输出一个整数：如果城市 $i$ 赢得比赛，购买所有票据的成本。

样例

输入 1

5
2 5 3 4 1
1 2 2
2 4 5
4 3 3
5 2 6

输出 1

130
159
191
163
171

输入 2

6
4 3 3 4 3 3
1 3 2
2 1 1
1 4 6
4 5 6
6 4 2

输出 2

209
206
232
209
336
232