Informatica Online Judge

  패셔니스타 정용이 [2132 / 0854]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 4   Total Tried : 4


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[34th 안민형]
Writer ID : [gs16054]

Background

정용이는 경곽 대표 패셔니스타다.
정용이는 매달마다 자신만의 새로운 패션을 선보여 모두를 유행시킨다. 오늘도 다음 달 자신의 패션을 고민하던 정용이는 문득 이런 생각이 들었다.

“과연 내가 최고의 패셔니스타가 맞을까? 나의 경쟁자가 나타나면 어떡하지?”

그래서 정용이는 각 학생마다 패션을 얼마나 많이 유행시키는지 알아보고자 한다.

유행은 우선 시작한 사람의 친구들에게로 전파되며, 그 친구들은 다시 각자의 친구들에게 유행시킨다. 즉, 친구가 많을수록 또 친할수록 빠르게 전파 시킬 수 있다. 단, 자신에게 유행을 권한 친구에게는 전파하지 않는다.

또한, 경곽의 친구 관계는 아주 특이해서, 한번 유행을 전파한 후에 누군가 다시 자신에게 유행을 권하는 경우는 없다고 한다. 따라서 친구 관계는 언제나 n-1개만이 존재한다.

또 다른 요소는 패션의 호감도이다. 패션의 호감도가 높을수록 더욱 빨리 전파된다.

그리고 각 사람은 유행을 받아들이면 동시에 자신의 친구들에게 유행을 전파하기 시작한다.
정용이가 경곽 학생 전체의 패션감각을 알아볼 수 있도록 도와주자.

Input

첫 줄에 경곽 전체 학생수 n(1<=n<=50000)이 주어진다.

다음 n-1줄에 각 학생의 친구 관계가 순서대로 주어진다. 세 수 a, b, c가 공백을 두고 입력되는데, a와 b는 각 친구의 번호( 정용이는 1번이다 )이며, c는 두 친구의 패션 친밀도이다.

패션 친밀도가 낮을수록 친하며, 유행을 전파하는데 패션 친밀도 만큼의 시간이 걸린다.
(1<=c<=100)

Output

n줄에 걸쳐 각 줄에 1번부터 n번까지의 친구들이 유행을 전파시키는데 걸리는 시간을 출력한다.

다음 줄에는 유행을 전파시키는 데 걸리는 시간이 가장 짧은 친구의 번호와 걸리는 시간을 공백을 두고 출력한다.

IO Example

입력1
10
2 1 96
3 2 18
4 1 62
5 3 51
6 3 88
7 3 38
8 3 8
9 2 18
10 9 61

출력1
202
158
176
264
227
264
214
184
176
237
2 158

입력2
10
2 1 100
3 1 54
4 1 79
5 1 34
6 2 54
7 2 85
8 5 95
9 1 80
10 7 22


출력2
207
229
261
286
241
283
314
336
287
336
1 207

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]