라디오 경품

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

트리랜드 지역은 n개의 도시로 이루어져 있고, n − 1개의 도로로 연결되어 있어 어떤 두 도시 사이에도 단순 경로가 정확히 하나씩 존재한다. i번째 도로는 도시 ui와 vi를 연결하고, 통행료는 wi다.

충성스러운 청취자에게 보답하기 위해 The Full Depth Morning Show가 여러 여행 상품을 나눠준다! Root와 Leaf는 팬레터를 가장 많이 보낸 도시에서 n − 1명의 운 좋은 주민을 뽑는다. 그런 다음 각 주민은 트리랜드의 서로 다른 도시로 가는 서로 다른 티켓을 하나씩 받는다.

트리랜드의 각 도시에는 상금에 대한 세금이 있다: ti. du,v를 도시 u에서 도시 v로 가는 유일한 단순 경로에 있는 각 도로의 통행료 합이라고 하자. 도시 u에서 도시 v로 가는 여행의 비용은 (tu + tv)du,v다.

Figure A.1: 첫 번째 샘플 입력에 대응하는 트리랜드 지도.

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

입력의 첫 줄에는 정수 n (1 ≤ n ≤ 100 000)이 주어진다. 다음 줄에는 n개의 공백으로 구분된 정수 ti (1 ≤ ti ≤ 1 000)가 주어지며, 이는 각 도시의 세금이다. 그다음 n − 1개 줄에는 각각 3개의 정수 ui, vi, wi가 주어지며, i번째 도로가 도시 ui와 vi (1 ≤ ui, vi ≤ n)를 연결하고 통행료가 wi (1 ≤ wi ≤ 1 000)라는 뜻이다.

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