시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 0 0 0 0.000%

## 문제

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}$. Figure 1: 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


## 출처 • 문제를 만든 사람: Arnav Sastry