# Full Depth Morning Show

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 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?

## Input

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

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

Sample Input 1 | Sample Output 1 |
---|---|

5 2 5 3 4 1 1 2 2 2 4 5 4 3 3 5 2 6 |
130 159 191 163 171 |

Sample Input 2 | Sample Output 2 |
---|---|

6 4 3 3 4 3 3 1 3 2 2 1 1 1 4 6 4 5 6 6 4 2 |
209 206 232 209 336 232 |