题目描述

All boring tree-shaped lands are alike, while all exciting tree-shaped lands are exciting in their own special ways. What makes Treeland more exciting than the other tree-shaped lands are the raddest radio hosts in the local area: Root and Leaf. Every morning on FM $32.33$ (repeating of course), Root and Leaf of The Full Depth Morning Show serve up the hottest celebrity gossip and traffic updates.

The region of Treeland is made of $n$ cities, connected by $n - 1$ roads such that between every pair of cities there is exactly one simple path. The $i$th road connects cities $u_i$ and $v_i$, and has a toll of $w_i$.

To reward their loyal listeners, The Full Depth Morning Show is giving away a number of travel packages! Root and Leaf will choose $n - 1$ lucky residents from the city that sends them the most fan mail. Each of those residents then gets a distinct ticket to a different city in Treeland.

Each city in Treeland has its own tax on prizes: $t_i$. Let $d_{u, v}$ be the sum of the tolls on each road on the only simple path from city $u$ to $v$. For a trip from city $u$ to city $v$, the cost of that trip is then $(t_u + t_v) d_{u, v}$.

The map of Treeland corresponding to the first sample input.

The shock jocks haven't quite thought through how much their prize is worth. They need to prepare a report to the radio executives, to summarize the expected costs. For each city that could win the prize, what is the total cost of purchasing all the tickets?

输入格式

The first line of input is a single integer $n$ ($1 \leq n \leq 100\,000$). The next line has $n$ space-separated integers $t_i$ ($1\leq t_i \leq 1\,000$), the tax in each city. The following $n - 1$ lines each have $3$ integers, $u_i, v_i, w_i$, meaning the $i$th road connects cities $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$), with a toll of $w_i$ ($1 \leq w_i \leq 1\,000$).

输出格式

Output $n$ lines. On the $i$th line, output a single integer: the cost of purchasing tickets if city $i$ wins the contest.

样例

输入样例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