로스팅하는 엠마는 바리스타입니다. 엠마는 N개의 정점을 가진 트리 형태의 농장 연결 시스템을 구축한 상태입니다. 트리의 정점은 1번부터 N번까지 번호가 매겨져 있습니다. 각각의 간선은 그 농장에서 다른 농장으로 이동할 수 있음을 뜻하며, 간선의 가중치는 이동 거리를 뜻합니다.

엠마는 한 개의 농장을 정해 농장 옆에 로스팅 시설을 마련하려고 합니다. 이때, 다른 농장에서 로스팅 시설까지의 거리의 합들을 알아야, 효율적으로 로스팅 시설의 위치를 정할 수 있을 것입니다. 그러므로 각각의 농장마다 다른 농장들에서 그 농장으로 가는 최단 거리들의 합을 구해줍시다.

입력 형식

첫째 줄에 N이 입력됩니다. (1 ≤ N ≤ 3 × 10⁵)

N-1 줄 동안 세 수 u, v 와 d가 주어집니다. 이는 u번째 농장과 v번째 농장은 서로 연결되어 있으며, 그 거리는 d임을 뜻합니다. (1 ≤ u, v ≤ N, 1 ≤ d ≤ 5)

주어지는 그래프는 트리입니다.

출력 형식

N개의 줄 동안 각각의 농장에 대해 다른 농장들에서 그 농장으로 가는 최단 거리들의 합을 출력합니다.

예제 입력

10
1 2 1
2 3 1
2 4 1
4 7 1
4 8 1
4 5 1
1 6 1
6 9 1
6 10 1

예제 출력

19
17
25
19
27
23
27
27
31
31