시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 111 43 36 58.065%

문제

철수는 항상 왼손을 붕대로 감고 다닌다. 붕대를 풀면 흑염룡이 날뛰어버리기 때문이다.

어느날 갑자기 철수가 살고 있는 국가에 태풍이 불어닥쳤다. 태풍으로 인해 주체할 수 없이 날뛰게 된 흑염룡을 잠재우기 위해 철수는 긴 여행을 떠나기로 결심했다. 흑염룡을 잠재우려면 태풍에게서 최대한 멀리 떨어져야 하기 때문에, 현재 철수가 살고 있는 국가에서 가장 거리가 먼 국가로 가야 한다.

철수가 사는 세계는 N개의 국가로 이루어져있고, 그 사이에는 N-1개의 도로가 있어서 국가들을 연결하고 있다. 각 도로는 두 국가를 양방향으로 연결한다. 그리고 임의의 국가에서 다른 모든 국가들로 가는 경로가 항상 존재한다.

철수가 살고 있는 국가의 번호가 i일 때, 철수의 여행의 목적지가 되는 국가까지의 거리를 D[i] 라고 하자. 1 ≤ i ≤ N 인 모든 i에 대해 D[i]를 알아내보자.

입력

첫째 줄에 국가의 수 N(2 ≤ N ≤ 50,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 도로의 정보가 주어진다. 각 도로의 정보는 from, to, length 으로 이루어져 있으며, 이 도로는 국가 from과 국가 to를 연결하는 도로이며 길이는 length 라는 뜻이다. (1 ≤ from, to ≤ N, from ≠ to, 1 ≤ length ≤ 40,000, length는 정수)

출력

i번째 줄에 D[i]의 값을 출력한다. (1 ≤ i ≤ N)

예제 입력 1

5
2 1 3
2 4 10
2 3 4
3 5 9

예제 출력 1

16
13
14
23
23

출처

  • 문제의 오타를 찾은 사람: eric00513
  • 문제를 만든 사람: ntopia