시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWM1ZDBcdWIyOTQgXHViYzM4XHViZTBjXHVhYzAwIFx1YjJlY1x1YjgyNFx1Yzc4OFx1YzViNFx1YzExYyZuYnNwO1x1YmIzY1x1Yzc3NCBcdWQ3NTBcdWI5NzRcdWM5YzAgXHVjNTRhXHViM2M0XHViODVkIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwO1x1Yzc3NCBcdWI1NGMsIFx1YWMwMSBcdWJjMzhcdWJlMGNcdWI5N2MgXHVjN2EwXHVhZGY4XHViMjk0IFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVkNzk4XHVjNzQwJm5ic3A7XHViMmU0XHViOTc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1ZDU3NFx1YmU0OFx1YzJkY1x1Yzc1OCBcdWFjZjVcdWJiMzRcdWM2ZDAgXHVjMmUwXHVkNTc0XHViZTQ4XHVjNzQwIFx1YzJhNFx1ZDUwNFx1YjljMVx1Y2ZlOFx1YjdlYyBcdWMyZGNcdWMyYTRcdWQxNWNcdWM3NDQgXHVjNjQ0XHViY2JkXHVkNTU4XHVhYzhjIFx1Yzc3NFx1ZDU3NFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWJjMzhcdWJlMGNcdWI5N2MgXHVjN2EwXHVhZGY4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWQ3OThcdWM3NTggXHVjNTkxXHVjNzQ0IFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1YzczY1x1Yjk3OCBcdWQ1NzRcdWJlNDhcdWM3NzRcdWIyOTQgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1ZDc5OFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzQgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWJjMzhcdWJlMGNcdWI5N2MgXHVjN2EwXHVhZDg4Jm5ic3A7XHViYWE4XHViNGUwIFx1YzJhNFx1ZDUwNFx1YjljMVx1Y2ZlOFx1YjdlY1x1YzVkMCBcdWJiM2NcdWM3NzQgXHVhY2Y1XHVhZTA5XHViNDE4XHVjOWMwIFx1YzU0YVx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZmNcdWM1ZjAgXHVkNzk4XHVjNzc0IFx1YzViY1x1YjljOFx1YjljY1x1ZDA3YyBcdWQ1NDRcdWM2OTRcdWQ1NjBcdWFlNGM/PFwvcD5cclxuXHJcblxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWIxNzhcdWI0ZGNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBOJm5ic3A7KDIgJmxlOyBOJm5ic3A7JmxlOyAxIDAwMClcdWFjZmMgXHVjOTExXHVjNTU5IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IEMmbmJzcDsoMSAmbGU7IEMmbmJzcDsmbGU7IE4pXHViODVjIFx1YzJkY1x1Yzc5MVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE4tMVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggdSwgdiZuYnNwOygxICZsZTsgdSwgdiAmbGU7IG4pIFx1YzY0MCZuYnNwO3cgKDEgJmxlOyB3ICZsZTsgMSAwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwmbmJzcDtcdWM3NzRcdWIyOTQgdVx1YzY0MCB2XHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHVhY2UwLCBcdWM3NzQgXHVkMzBjXHVjNzc0XHVkNTA0XHVjNzU4IFx1YmMzOFx1YmUwY1x1Yjk3YyBcdWM3YTBcdWFkZjhcdWIyOTQgXHViMzcwIHdcdWI5Y2NcdWQwN2NcdWM3NTggXHVkNzk4XHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlOCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViYWE4XHViNGUwIFx1YzJhNFx1ZDUwNFx1YjljMVx1Y2ZlOFx1YjdlY1x1Yjg1YyBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1YmIzY1x1Yzc3NCBcdWQ3NThcdWI3ZWNcdWI0ZTRcdWM1YjRcdWFjMDBcdWM5YzAgXHVjNTRhXHViM2M0XHViODVkIFx1YmMzOFx1YmUwY1x1Yjk3YyBcdWM3YTBcdWFkZjhcdWIyOTQgXHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHVkNzk4XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5Mjc5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRnJvemVuIFJvc2UtSGVhZHMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSB3aW50ZXIgaXMgY29taW5nIGFuZCBhbGwgdGhlIGV4cGVydHMgYXJlIHdhcm5pbmcgdGhhdCBpdCB3aWxsIGJlIHRoZSBjb2xkZXN0IG9uZSBpbiB0aGUgbGFzdCBodW5kcmVkIHllYXJzLiBGcmVkZHkgbmVlZHMgdG8gbWFrZSBzdXJlIHRoYXQgaGlzIGdhcmRlbiBkb2VzIG5vdCBzdXN0YWluIGFueSBkYW1hZ2UuIE9uZSBvZiB0aGUgbW9zdCBpbXBvcnRhbnQgdGFza3MgaXMgdG8gbWFrZSBzdXJlIHRoYXQgbm8gd2F0ZXIgcmVtYWlucyBpbiBoaXMgbGFyZ2Ugd2F0ZXJpbmcgc3lzdGVtLjxcL3A+XHJcblxyXG48cD5BbGwgdGhlIHdhdGVyIGNvbWVzIGZyb20gYSBjZW50cmFsIG5vZGUgYW5kIGlzIGRpc3RyaWJ1dGVkIGJ5IHBpcGVzIHRvIG5laWdoYm9yaW5nIG5vZGVzIGFuZCBzbyBvbi4gRWFjaCBub2RlIGlzIGVpdGhlciBhIHNwcmlua2xlciAocm9zZSBoZWFkKSB3aXRoIG5vIG91dGdvaW5nIHBpcGUgb3IgYW4gaW50ZXJuYWwgbm9kZSB3aXRoIG9uZSBvciBtb3JlIG91dGdvaW5nIHBpcGVzIGxlYWRpbmcgdG8gc29tZSBvdGhlciBub2Rlcy4gRXZlcnkgbm9kZSBoYXMgZXhhY3RseSBvbmUgaW5jb21pbmcgcGlwZSwgZXhjZXB0IGZvciB0aGUgY2VudHJhbCBub2RlIHdoaWNoIHRha2VzIHRoZSB3YXRlciBkaXJlY3RseSBmcm9tIGEgd2VsbCBhbmQgaGFzIG5vIGluY29taW5nIHBpcGUuIEV2ZXJ5IHBpcGUgaGFzIGEgdmFsdmUgdGhhdCBzdG9wcyBhbGwgdGhlIHdhdGVyIGdvaW5nIHRocm91Z2ggdGhlIHBpcGUuIFRoZSB2YWx2ZXMgYXJlIG9mIGRpXHVmYjAwZXJlbnQgcXVhbGl0eSBhbmQgYWdlLCBzbyBzb21lIG1heSBiZSBoYXJkZXIgdG8gY2xvc2UgdGhhbiBvdGhlcnMuPFwvcD5cclxuXHJcbjxwPkZyZWRkeSBrbm93cyBoaXMgdmFsdmVzIHdlbGwgYW5kIGhhcyBhc3NpZ25lZCBhIHZhbHVlIHRvIGVhY2ggcGlwZSByZXByZXNlbnRpbmcgdGhlIGFtb3VudCBvZiBlXHVmYjAwb3J0IG5lZWRlZCB0byBjbG9zZSB0aGUgY29ycmVzcG9uZGluZyB2YWx2ZS4gSGUgYXNrcyB5b3UgdG8gaGVscCBoaW0gY291bnQgdGhlIG1pbmltdW0gZVx1ZmIwMG9ydCBuZWVkZWQgdG8gY2xvc2Ugc29tZSB2YWx2ZXMgc28gdGhhdCBubyB3YXRlciBnb2VzIHRvIHRoZSBzcHJpbmtsZXJzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIHdpdGggdHdvIGludGVnZXJzLCB0aGUgbnVtYmVyIG9mIG5vZGVzIG4gKDIgJmxlOyBuICZsZTsgMSAwMDApLCBhbmQgdGhlIG51bWJlciBvZiB0aGUgY2VudHJhbCBub2RlIGMgKDEgJmxlOyBjICZsZTsgbikuIEVhY2ggb2YgdGhlIG5leHQgbiAmbWludXM7IDEgbGluZXMgcmVwcmVzZW50cyBvbmUgcGlwZSBhbmQgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMsIHUsIHYgKDEgJmxlOyB1LCB2ICZsZTsgbikgYW5kIHcgKDEgJmxlOyB3ICZsZTsgMSAwMDApLCB3aGVyZSB1IGFuZCB2IGFyZSB0aGUgbm9kZXMgY29ubmVjdGVkIGJ5IGEgcGlwZSBhbmQgdyBpcyB0aGUgZVx1ZmIwMG9ydCBuZWVkZWQgdG8gY2xvc2UgdGhlIHZhbHZlIG9uIHRoYXQgcGlwZS4gWW91IG1heSBhc3N1bWUgdGhhdCBldmVyeSBub2RlIGlzIHJlYWNoYWJsZSBmcm9tIHRoZSBjZW50cmFsIG5vZGUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBtaW5pbXVtIHN1bSBvZiBlXHVmYjAwb3J0cyBvZiB2YWx2ZXMgdG8gYmUgY2xvc2VkLCBzdWNoIHRoYXQgdGhlIGNlbnRyYWwgbm9kZSBnZXRzIHNlcGFyYXRlZCBmcm9tIGFsbCBzcHJpbmtsZXJzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==