시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 59 24 17 34.694%

문제

이번 겨울은 100년 만에 가장 추운 겨울이라고 한다. 해빈시는 겨울을 대비해서 공원이 망가지지 않다로고 조치를 취하려고 한다. 가장 먼저 스프링쿨러에 남아있는 물을 제거해야 한다. 

중앙 노드에서 분배된 물은 모두 파이프를 통해 이웃한 노드로 흘러간다. 모든 노드는 스프링쿨러이거나 물을 분배하는 내부 노드이다. 자세한 설명은 아래에 나와있다.

  • 우물과 직접 연결된 중앙 노드를 제외한 모든 노드는 모두 물을 공급받는 파이프를 단 하나 가지고 있다.
  • 모든 내부 노드는 다른 노드로 물을 분배하는 파이프를 하나 이상 가지고 있다. 즉, 스프링클러는 물을 내보내는 파이프를 가지고 있지 않다.
  • 모든 파이프에는 밸브가 달려있어서 물이 흐르지 않도록 할 수 있다. 이때, 각 밸브를 잠그는 데 필요한 힘은 다르다.

해빈시의 공무원 신해빈은 스프링쿨러 시스템을 완벽하게 이해하고 있고, 각 밸브를 잠그는데 필요한 힘의 양을 알고 있다.

게으른 해빈이는 최소한의 힘을 사용해 몇 개의 밸브를 잠궈 모든 스프링쿨러에 물이 공급되지 않도록 하려고 한다.

과연 힘이 얼마만큼 필요할까?

입력

입력은 여러 개의 테스트 케이스로 이루어져있다.

각 테스트 케이스는 노드의 개수를 나타내는 N (2 ≤ N ≤ 1 000)과 중앙 노드의 번호를 나타내는 C (1 ≤ C ≤ N)로 시작된다.

이후 N-1개의 줄에는 각 파이프의 정보를 나타내는 세 정수 u, v (1 ≤ u, v ≤ n) 와 w (1 ≤ w ≤ 1 000)가 주어지는데, 이는 u와 v를 연결하는 파이프가 존재하고, 이 파이프의 밸브를 잠그는 데 w만큼의 힘이 필요하단 뜻이다.

출력

각 테스트 케이스마다 모든 스프링쿨러로 더 이상 물이 흘러들어가지 않도록 밸브를 잠그는 데 필요한 최소한의 힘을 출력한다.

예제 입력 1

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

예제 출력 1

9
5
W3sicHJvYmxlbV9pZCI6IjkyNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1YmNcdWM1YjRcdWJkOTlcdWM3NDAgXHVjMmE0XHVkNTA0XHViOWMxXHVjZmU4XHViN2VjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzRcdWJjODggXHVhY2E4XHVjNmI4XHVjNzQwIDEwMFx1YjE0NCBcdWI5Y2NcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1Y2Q5NFx1YzZiNCBcdWFjYThcdWM2YjhcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ1NzRcdWJlNDhcdWMyZGNcdWIyOTQgXHVhY2E4XHVjNmI4XHVjNzQ0IFx1YjMwMFx1YmU0NFx1ZDU3NFx1YzExYyBcdWFjZjVcdWM2ZDBcdWM3NzQgXHViOWRkXHVhYzAwXHVjOWMwXHVjOWMwIFx1YzU0YVx1YjJlNFx1Yjg1Y1x1YWNlMCBcdWM4NzBcdWNlNThcdWI5N2MgXHVjZGU4XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YmEzY1x1YzgwMCBcdWMyYTRcdWQ1MDRcdWI5YzFcdWNmZThcdWI3ZWNcdWM1ZDAgXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1YmIzY1x1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM5MTFcdWM1NTkgXHViMTc4XHViNGRjXHVjNWQwXHVjMTFjIFx1YmQ4NFx1YmMzMFx1YjQxYyBcdWJiM2NcdWM3NDAgXHViYWE4XHViNDUwIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yjk3YyBcdWQxYjVcdWQ1NzQgXHVjNzc0XHVjNmMzXHVkNTVjIFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWQ3NThcdWI3ZWNcdWFjMDRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWIxNzhcdWI0ZGNcdWIyOTQgXHVjMmE0XHVkNTA0XHViOWMxXHVjZmU4XHViN2VjXHVjNzc0XHVhYzcwXHViMDk4IFx1YmIzY1x1Yzc0NCBcdWJkODRcdWJjMzBcdWQ1NThcdWIyOTQgXHViMGI0XHViZDgwIFx1YjE3OFx1YjRkY1x1Yzc3NFx1YjJlNC4gXHVjNzkwXHVjMTM4XHVkNTVjIFx1YzEyNFx1YmE4NVx1Yzc0MCBcdWM1NDRcdWI3OThcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzZiMFx1YmIzY1x1YWNmYyBcdWM5YzFcdWM4MTEgXHVjNWYwXHVhY2IwXHViNDFjIFx1YzkxMVx1YzU1OSBcdWIxNzhcdWI0ZGNcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWIxNzhcdWI0ZGNcdWIyOTQgXHViYWE4XHViNDUwIFx1YmIzY1x1Yzc0NCBcdWFjZjVcdWFlMDlcdWJjMWJcdWIyOTQgXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1YjJlOCBcdWQ1NThcdWIwOTggXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YjBiNFx1YmQ4MCBcdWIxNzhcdWI0ZGNcdWIyOTQgXHViMmU0XHViOTc4IFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWJiM2NcdWM3NDQgXHViZDg0XHViYzMwXHVkNTU4XHViMjk0IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yjk3YyBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuJm5ic3A7XHVjOTg5LCBcdWMyYTRcdWQ1MDRcdWI5YzFcdWQwNzRcdWI3ZWNcdWIyOTQgXHViYjNjXHVjNzQ0IFx1YjBiNFx1YmNmNFx1YjBiNFx1YjI5NCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWM1ZDBcdWIyOTQgXHViYzM4XHViZTBjXHVhYzAwIFx1YjJlY1x1YjgyNFx1Yzc4OFx1YzViNFx1YzExYyZuYnNwO1x1YmIzY1x1Yzc3NCBcdWQ3NTBcdWI5NzRcdWM5YzAgXHVjNTRhXHViM2M0XHViODVkIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwO1x1Yzc3NFx1YjU0YywgXHVhYzAxIFx1YmMzOFx1YmUwY1x1Yjk3YyBcdWM3YTBcdWFkZjhcdWIyOTQgXHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWQ3OThcdWM3NDAmbmJzcDtcdWIyZTRcdWI5NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkNTc0XHViZTQ4XHVjMmRjXHVjNzU4IFx1YWNmNVx1YmIzNFx1YzZkMCBcdWMyZTBcdWQ1NzRcdWJlNDhcdWM3NDAgXHVjMmE0XHVkNTA0XHViOWMxXHVjZmU4XHViN2VjIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0NCBcdWM2NDRcdWJjYmRcdWQ1NThcdWFjOGMgXHVjNzc0XHVkNTc0XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YmMzOFx1YmUwY1x1Yjk3YyBcdWM3YTBcdWFkZjhcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1ZDc5OFx1Yzc1OCBcdWM1OTFcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzNjXHViOTc4IFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHVkNzk4XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YmMzOFx1YmUwY1x1Yjk3YyBcdWM3YTBcdWFkODgmbmJzcDtcdWJhYThcdWI0ZTAgXHVjMmE0XHVkNTA0XHViOWMxXHVjZmU4XHViN2VjXHVjNWQwIFx1YmIzY1x1Yzc3NCBcdWFjZjVcdWFlMDlcdWI0MThcdWM5YzAgXHVjNTRhXHViM2M0XHViODVkIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmY1x1YzVmMCBcdWQ3OThcdWM3NzQgXHVjNWJjXHViOWM4XHViOWNjXHVkMDdjIFx1ZDU0NFx1YzY5NFx1ZDU2MFx1YWU0Yz88XC9wPlxyXG5cclxuXHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzhcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IE4mbmJzcDsoMiAmbGU7IE4mbmJzcDsmbGU7IDEgMDAwKVx1YWNmYyBcdWM5MTFcdWM1NTkgXHViMTc4XHViNGRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgQyZuYnNwOygxICZsZTsgQyZuYnNwOyZsZTsgTilcdWI4NWMgXHVjMmRjXHVjNzkxXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTi0xXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkMzBjXHVjNzc0XHVkNTA0XHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCB1LCB2Jm5ic3A7KDEgJmxlOyB1LCB2ICZsZTsgbikgXHVjNjQwJm5ic3A7dyAoMSAmbGU7IHcgJmxlOyAxIDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCZuYnNwO1x1Yzc3NFx1YjI5NCB1XHVjNjQwIHZcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWFjZTAsIFx1Yzc3NCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWM3NTggXHViYzM4XHViZTBjXHViOTdjIFx1YzdhMFx1YWRmOFx1YjI5NCBcdWIzNzAgd1x1YjljY1x1ZDA3Y1x1Yzc1OCBcdWQ3OThcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU4IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWJhYThcdWI0ZTAgXHVjMmE0XHVkNTA0XHViOWMxXHVjZmU4XHViN2VjXHViODVjIFx1YjM1NCBcdWM3NzRcdWMwYzEgXHViYjNjXHVjNzc0IFx1ZDc1OFx1YjdlY1x1YjRlNFx1YzViNFx1YWMwMFx1YzljMCBcdWM1NGFcdWIzYzRcdWI4NWQgXHViYzM4XHViZTBjXHViOTdjIFx1YzdhMFx1YWRmOFx1YjI5NCBcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWQ3OThcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkyNzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGcm96ZW4gUm9zZS1IZWFkcyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHdpbnRlciBpcyBjb21pbmcgYW5kIGFsbCB0aGUgZXhwZXJ0cyBhcmUgd2FybmluZyB0aGF0IGl0IHdpbGwgYmUgdGhlIGNvbGRlc3Qgb25lIGluIHRoZSBsYXN0IGh1bmRyZWQgeWVhcnMuIEZyZWRkeSBuZWVkcyB0byBtYWtlIHN1cmUgdGhhdCBoaXMgZ2FyZGVuIGRvZXMgbm90IHN1c3RhaW4gYW55IGRhbWFnZS4gT25lIG9mIHRoZSBtb3N0IGltcG9ydGFudCB0YXNrcyBpcyB0byBtYWtlIHN1cmUgdGhhdCBubyB3YXRlciByZW1haW5zIGluIGhpcyBsYXJnZSB3YXRlcmluZyBzeXN0ZW0uPFwvcD5cclxuXHJcbjxwPkFsbCB0aGUgd2F0ZXIgY29tZXMgZnJvbSBhIGNlbnRyYWwgbm9kZSBhbmQgaXMgZGlzdHJpYnV0ZWQgYnkgcGlwZXMgdG8gbmVpZ2hib3Jpbmcgbm9kZXMgYW5kIHNvIG9uLiBFYWNoIG5vZGUgaXMgZWl0aGVyIGEgc3ByaW5rbGVyIChyb3NlIGhlYWQpIHdpdGggbm8gb3V0Z29pbmcgcGlwZSBvciBhbiBpbnRlcm5hbCBub2RlIHdpdGggb25lIG9yIG1vcmUgb3V0Z29pbmcgcGlwZXMgbGVhZGluZyB0byBzb21lIG90aGVyIG5vZGVzLiBFdmVyeSBub2RlIGhhcyBleGFjdGx5IG9uZSBpbmNvbWluZyBwaXBlLCBleGNlcHQgZm9yIHRoZSBjZW50cmFsIG5vZGUgd2hpY2ggdGFrZXMgdGhlIHdhdGVyIGRpcmVjdGx5IGZyb20gYSB3ZWxsIGFuZCBoYXMgbm8gaW5jb21pbmcgcGlwZS4gRXZlcnkgcGlwZSBoYXMgYSB2YWx2ZSB0aGF0IHN0b3BzIGFsbCB0aGUgd2F0ZXIgZ29pbmcgdGhyb3VnaCB0aGUgcGlwZS4gVGhlIHZhbHZlcyBhcmUgb2YgZGlcdWZiMDBlcmVudCBxdWFsaXR5IGFuZCBhZ2UsIHNvIHNvbWUgbWF5IGJlIGhhcmRlciB0byBjbG9zZSB0aGFuIG90aGVycy48XC9wPlxyXG5cclxuPHA+RnJlZGR5IGtub3dzIGhpcyB2YWx2ZXMgd2VsbCBhbmQgaGFzIGFzc2lnbmVkIGEgdmFsdWUgdG8gZWFjaCBwaXBlIHJlcHJlc2VudGluZyB0aGUgYW1vdW50IG9mIGVcdWZiMDBvcnQgbmVlZGVkIHRvIGNsb3NlIHRoZSBjb3JyZXNwb25kaW5nIHZhbHZlLiBIZSBhc2tzIHlvdSB0byBoZWxwIGhpbSBjb3VudCB0aGUgbWluaW11bSBlXHVmYjAwb3J0IG5lZWRlZCB0byBjbG9zZSBzb21lIHZhbHZlcyBzbyB0aGF0IG5vIHdhdGVyIGdvZXMgdG8gdGhlIHNwcmlua2xlcnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMsIHRoZSBudW1iZXIgb2Ygbm9kZXMgbiAoMiAmbGU7IG4gJmxlOyAxIDAwMCksIGFuZCB0aGUgbnVtYmVyIG9mIHRoZSBjZW50cmFsIG5vZGUgYyAoMSAmbGU7IGMgJmxlOyBuKS4gRWFjaCBvZiB0aGUgbmV4dCBuICZtaW51czsgMSBsaW5lcyByZXByZXNlbnRzIG9uZSBwaXBlIGFuZCBjb250YWlucyB0aHJlZSBpbnRlZ2VycywgdSwgdiAoMSAmbGU7IHUsIHYgJmxlOyBuKSBhbmQgdyAoMSAmbGU7IHcgJmxlOyAxIDAwMCksIHdoZXJlIHUgYW5kIHYgYXJlIHRoZSBub2RlcyBjb25uZWN0ZWQgYnkgYSBwaXBlIGFuZCB3IGlzIHRoZSBlXHVmYjAwb3J0IG5lZWRlZCB0byBjbG9zZSB0aGUgdmFsdmUgb24gdGhhdCBwaXBlLiBZb3UgbWF5IGFzc3VtZSB0aGF0IGV2ZXJ5IG5vZGUgaXMgcmVhY2hhYmxlIGZyb20gdGhlIGNlbnRyYWwgbm9kZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1pbmltdW0gc3VtIG9mIGVcdWZiMDBvcnRzIG9mIHZhbHZlcyB0byBiZSBjbG9zZWQsIHN1Y2ggdGhhdCB0aGUgY2VudHJhbCBub2RlIGdldHMgc2VwYXJhdGVkIGZyb20gYWxsIHNwcmlua2xlcnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d