시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 397 133 83 27.759%

문제

트리는 사이클을 갖지 않는 연결된 그래프이다.

중앙 정점은 모든 정점으로 이르는 비용의 합이 가장 작은 정점이다. 트리의 정점 개수가 작은 경우에는 모든 경우의 수를 다 계산해보는 프로그램을 이용해 쉽게 구할 수 있다.

위의 그림은 가중치가 있는 트리로, 정점의 개수는 5개이다. 이 트리의 중앙 정점은 B이다.

B-A = 2, B-D = 7, B-C = 1, B-E = 7+5=12, 총: 2+1+7+12 = 22

N이 큰 경우에 문제를 풀어보자.

트리를 입력 받아, 모든 정점과 중앙 정점까지 비용의 합을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄에는 세 정수 a, b, w가 주어진다. (1 ≤ w ≤ 100) a와 b는 간선을 나타내고, w는 그 간선의 가중치이다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 모든 정점과 중앙 정점 사이의 비용의 합을 출력한다.

예제 입력 1

5
0 1 2
1 2 1
1 3 7
3 4 5
6
0 1 1
1 2 4
2 3 1
3 4 4
4 5 1
0

예제 출력 1

22
21
W3sicHJvYmxlbV9pZCI6Ijc4MTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5MTFcdWM1NTkgXHVkMmI4XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQyYjhcdWI5YWNcdWIyOTQgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzQ0IFx1YWMxNlx1YzljMCBcdWM1NGFcdWIyOTQgXHVjNWYwXHVhY2IwXHViNDFjIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTExXHVjNTU5IFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1Yjk3NFx1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjODE1XHVjODEwXHVjNzc0XHViMmU0LiBcdWQyYjhcdWI5YWNcdWM3NTggXHVjODE1XHVjODEwIFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM3OTFcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YjJlNCBcdWFjYzRcdWMwYjBcdWQ1NzRcdWJjZjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWMyN2RcdWFjOGMgXHVhZDZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHJlZW1lZGlhbi5naWZcIiBzdHlsZT1cImhlaWdodDoxNTZweDsgb3BhY2l0eTowLjk7IHdpZHRoOjI1MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVhYzAwXHVjOTExXHVjZTU4XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWQyYjhcdWI5YWNcdWI4NWMsIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgNVx1YWMxY1x1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWM5MTFcdWM1NTkgXHVjODE1XHVjODEwXHVjNzQwIEJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkItQSA9IDIsIEItRCA9IDcsIEItQyA9IDEsIEItRSA9IDcrNT0xMiwgXHVjZDFkOiAyKzErNysxMiA9IDIyPFwvcD5cclxuXHJcbjxwPk5cdWM3NzQgXHVkMDcwIFx1YWNiZFx1YzZiMFx1YzVkMCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwXHVjNWI0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWQyYjhcdWI5YWNcdWI5N2MgXHVjNzg1XHViODI1IFx1YmMxYlx1YzU0NCwgXHViYWE4XHViNGUwIFx1YzgxNVx1YzgxMFx1YWNmYyBcdWM5MTFcdWM1NTkgXHVjODE1XHVjODEwXHVhZTRjXHVjOWMwIFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwLDAwMCkgXHVhYzAxIFx1YzgxNVx1YzgxMFx1Yzc0MCAwXHViYzg4XHViZDgwXHVkMTMwIG4tMVx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMmU0XHVjNzRjIG4tMVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBhLCBiLCB3XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyB3ICZsZTsgMTAwKSBhXHVjNjQwIGJcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgd1x1YjI5NCBcdWFkZjggXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViYWE4XHViNGUwIFx1YzgxNVx1YzgxMFx1YWNmYyBcdWM5MTFcdWM1NTkgXHVjODE1XHVjODEwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWJlNDRcdWM2YTlcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3ODEyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJlZSBNZWRpYW4iLCJkZXNjcmlwdGlvbiI6IjxwPkEgdHJlZSBpcyBhIGNvbm5lY3RlZCBncmFwaCBjb250YWluaW5nIG5vIGN5Y2xlcy4gQSB2ZXJ0ZXggaXMgY2FsbGVkIGEgbWVkaWFuIHZlcnRleCBpZiB0aGUgdG90YWwgY29zdCB0byByZWFjaCBhbGwgdmVydGljZXMgaXMgbWluaW1hbC4gVGhlcmUgY291bGQgYmUgbW9yZSB0aGFuIG9uZSBtZWRpYW4gdmVydGV4IGluIGEgdHJlZSwgdGhhdCZyc3F1bztzIHdoeSB3ZSBkZWZpbmUgbWVkaWFuIGFzIHRoZSBzZXQgb2YgYWxsIG1lZGlhbiB2ZXJ0aWNlcy4gVG8gZmluZCBtZWRpYW4gaW4gYSB0cmVlIHdpdGggc21hbGwgbnVtYmVyIG9mIHZlcnRpY2VzIGlzIGZhaXJseSBlYXN5IHRhc2sgYXMgeW91IGNhbiBzb2x2ZSB0aGlzIGJ5IGEgc2ltcGxlIGJydXRlIGZvcmNlIHByb2dyYW0uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHJlZW1lZGlhbi5naWZcIiBzdHlsZT1cImZsb2F0OmxlZnQ7IGhlaWdodDoxNTZweDsgd2lkdGg6MjUwcHhcIiBcLz5JbiB0aGUgbGVmdCBmaWd1cmUsIHdlIGNhbiBzZWUgYSB3ZWlnaHRlZCB0cmVlIHdpdGggNSB2ZXJ0aWNlcy4gVGhlIHRyZWUgbWVkaWFuIGlzIHtCfSBiZWNhdXNlIHRoZSB0b3RhbCBjb3N0IGZyb20gdmVydGV4IEIgdG8gYWxsIG90aGVyIHZlcnRpY2VzIGlzIG1pbmltYWwuPFwvcD5cclxuXHJcbjxwPkItQSA9IDIgJm5ic3A7ICZuYnNwO0ItRCA9IDc8YnIgXC8+XHJcbkItQyA9IDEgJm5ic3A7ICZuYnNwO0ItRSA9IDcgKyA1ID0gMTI8XC9wPlxyXG5cclxuPHA+VE9UQUwgPSAyICsgMSArIDcgKyAxMiA9IDIyPFwvcD5cclxuXHJcbjxwPldoYXQgaWYgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBpcyBxdWl0ZSBsYXJnZT8gVGhpcyBtaWdodCBiZSBhIHByb2JsZW0gc2luY2UgYnJ1dGUgZm9yY2UgcHJvZ3JhbSBjb3N0IHRvbyBtdWNoIHRpbWUuIEdpdmVuIGEgd2VpZ2h0ZWQgdHJlZSB3aXRoIE4gdmVydGljZXMsIG91dHB1dCB0aGUgdG90YWwgY29zdCB0byByZWFjaCBhbGwgdmVydGljZXMgZnJvbSBpdHMgbWVkaWFuLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgY29uc2lzdHMgb2Ygc2V2ZXJhbCBjYXNlcy4gRWFjaCBjYXNlIGJlZ2lucyB3aXRoIGFuIGludGVnZXIgbiAoMSZsdDs9IG4gJmx0Oz0gMTAsMDAwKSBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIGEgdHJlZS4gRWFjaCB2ZXJ0ZXggaXMgbnVtYmVyZWQgZnJvbSAwLi4ubi0xLiBFYWNoIG9mIHRoZSBuZXh0IG4tMSBsaW5lcyBjb250YWlucyB0aHJlZSBpbnRlZ2VyczogYSwgYiwgYW5kIHcgKDEmbHQ7PSB3ICZsdDs9IDEwMCksIHdoaWNoIG1lYW5zIGEgYW5kIGIgaXMgY29ubmVjdGVkIGJ5IGFuIGVkZ2Ugd2l0aCB3ZWlnaHQgdy48XC9wPlxyXG5cclxuPHA+SW5wdXQgaXMgdGVybWluYXRlZCB3aGVuIG4gaXMgZXF1YWwgdG8gMC4gVGhpcyBpbnB1dCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjYXNlLCBvdXRwdXQgYSBsaW5lIGNvbnRhaW5pbmcgdGhlIHN1bSBvZiBjb3N0IG9mIHBhdGggdG8gYWxsIG90aGVyIHZlcnRpY2VzIGZyb20gdGhlIHRyZWUgbWVkaWFuLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=