Full Depth Morning Show

지루한 나무 모양의 땅은 모두 비슷하지만, 흥미로운 나무 모양의 땅은 저마다 특별한 방식으로 흥미롭다. Treeland를 다른 나무 모양의 땅보다 흥미롭게 만드는 것은 이 지역 최고의 라디오 진행자 Root와 Leaf다. 매일 아침 FM $32.33$(당연히 반복되는 소수)에서 The Full Depth Morning Show의 Root와 Leaf가 가장 뜨거운 연예인 가십과 교통 정보를 전한다.

Treeland는 $n$개의 도시로 이루어져 있고, $n - 1$개의 도로가 도시들을 연결하므로 어떤 두 도시 사이에도 단순 경로가 정확히 하나씩 존재한다. $i$번째 도로는 도시 $u\_i$와 $v\_i$를 연결하며 통행료가 $w\_i$다.

충성스러운 청취자에게 보답하기 위해 The Full Depth Morning Show가 여러 여행 패키지를 선물한다! Root와 Leaf는 팬레터를 가장 많이 보낸 도시에서 $n - 1$명의 행운의 주민을 뽑는다. 그런 다음 각 주민은 Treeland의 서로 다른 도시로 가는 서로 다른 티켓을 하나씩 받는다.

Treeland의 각 도시에는 상금에 대한 세금 $t\_i$가 있다. $d\_{u, v}$를 도시 $u$에서 $v$로 가는 유일한 단순 경로에 있는 모든 도로의 통행료 합이라고 하자. 도시 $u$에서 도시 $v$로 가는 여행의 비용은 $(t\_u + t\_v) d\_{u, v}$다.

그림 1: 첫 번째 샘플 입력에 대응하는 Treeland의 지도.

충격적인 진행자들은 자신들의 상금이 얼마나 가치가 있는지 충분히 생각하지 않았다. 그들은 예상 비용을 요약한 보고서를 라디오 경영진에 제출해야 한다. 상금을 받을 수 있는 각 도시마다, 모든 티켓을 사는 데 드는 총비용은 얼마인가?

첫 줄에는 정수 $n$이 하나 주어진다($1 \leq n \leq 100\,000$). 다음 줄에는 각 도시의 세금을 나타내는 $n$개의 정수 $t\_i$가 공백으로 구분되어 주어진다($1\leq t\_i \leq 1\,000$). 그다음 $n - 1$개의 줄에는 각각 $3$개의 정수 $u\_i, v\_i, w\_i$가 주어지며, 이는 $i$번째 도로가 도시 $u\_i$와 $v\_i$를 연결하고 통행료가 $w\_i$임을 뜻한다($1 \le u\_i, v\_i \le n$, $1 \leq w\_i \leq 1\,000$).

$n$개의 줄을 출력한다. $i$번째 줄에는 도시 $i$가 콘테스트에서 이겼을 때 티켓을 사는 데 드는 비용을 정수 하나로 출력한다.