우주여행 1초 512MB
문제
윤서는 KOI우주연합의 제법 잘나가는 우주여행가다.
최근 윤서의 가장 큰 취미는 가장 먼 곳까지 여행을 가는 것이다.
KOI우주연합은 N개의 은하들로 이루어져 있는데, 그 사이에는 N-1개의 웜홀이 있어서 은하들을 오고 갈 수 있게 되어있다. 각 웜홀은 두 은하를 양방향으로 연결하며, 웜홀의 길이는 다를 수 있다. 그리고 임의의 은하에서 다른 모든 은하들로 가는 경로가 항상 존재한다.
윤서가 현재 위치한 은하의 번호가 i일 때, 윤하의 취미 생활을 위해 가장 먼 곳 까지 여행을 했을 때의 목적지가 되는 은하까지의 거리를 D[i]라고 한다면, 1 ≤ i ≤ N 인 모든 i에 대해 D[i]를 모두 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 KOI우주연합에 속한 은하의 수 N이 주어진다. (2 ≤ N ≤ 50,000)
둘 번째 줄부터 N-1개의 줄에 웜홀의 정보가 주어진다. 각 웜홀의 정보는 웜홀이 연결하는 두 은하 A와 B, 그리고 그 사이의 거리 K로 이루어져 있다. (1 ≤ A,B ≤ N, A ≠ B, 1 ≤ K ≤ 40,000)
이 때, 모든 입력값은 정수이다.
출력
i번째 줄에 D[i]의 값을 출력한다. (1 ≤ i ≤ N)
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 7점 | N ≤ 3 |
| #2 | 23점 | N ≤ 1,000 |
| #3 | 70점 | 추가 제한 없음 |
예제
5
2 1 3
2 4 10
2 3 4
3 5 9
16
13
14
23
23
로그인해야 코드를 작성할 수 있어요.