시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 192 67 52 33.333%

문제

오늘 팀전을 다들 열심히 하시는 것을 보고 원장선생님은 세미나 실에 인터넷을 설치해 주기로 마음을 먹으셨다. 하지만 비 협조적인 코레스코 콘도는 원장님께서 학생들에게 인터넷 선을 연결하는 것에 대해서 일부에 대해 돈을 요구하였다.

각각의 학생들의 번호가 1부터 N까지 붙여져 있다고 하면 아무나 서로 인터넷 선이 연결되어 있지 않다. P(P<=10,000)개의 쌍만이 서로 이어 질수 있으며 서로 선을 연결하는데 가격이 다르다.

1번은 다행이 인터넷 서버와 바로 연결되어 있어 인터넷이 가능하다. 우리의 목표는 N번 컴퓨터가 인터넷에 연결되도록 하는 것이다. 나머지 컴퓨터는 연결 되있거나 연결 안되어있어도 무방하다.

하지만 코레스코에서는 K개의 인터넷 선에 대해서는 공짜로 연결해주기로 하였다. 그리고 나머지 인터넷 선에 대해서는 남은 것 중 제일 가격이 비싼 것에 대해서만 가격을 받기로 하였다. 이때 원장선생님이 내게 되는 최소의 값을 구하여라.

입력

첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차례로 들어온다. 가격은 1 이상 1,000,000 이하다.

출력

첫째줄에 원장선생님이 내게 되는 최소의 돈와 만약 1번과 N번 컴퓨터를 잇는 것이 불가능 하다면 -1을 출력하라.

예제 입력 1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

예제 출력 1

4

힌트

1-3 3-2 2-5을 이용하여 인터넷을 연결한다면 그 가격들은 4 3 9원이 나오게 된다.

하지만 코레스코에서 1개의 케이블은 무상으로 주니까 9원짜리를 뺀 것 중 가장 큰 가격은 4가 된다.

W3sicHJvYmxlbV9pZCI6IjE4MDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzhcdWQxMzBcdWIxMzcgXHVjMTI0XHVjZTU4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MjRcdWIyOTggXHVkMzAwXHVjODA0XHVjNzQ0IFx1YjJlNFx1YjRlNCBcdWM1ZjRcdWMyZWNcdWQ3ODggXHVkNTU4XHVjMmRjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjZjRcdWFjZTAgXHVjNmQwXHVjN2E1XHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1YzEzOFx1YmJmOFx1YjA5OCBcdWMyZTRcdWM1ZDAgXHVjNzc4XHVkMTMwXHViMTM3XHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU3NCBcdWM4ZmNcdWFlMzBcdWI4NWMgXHViOWM4XHVjNzRjXHVjNzQ0IFx1YmEzOVx1YzczY1x1YzE2OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YmU0NCBcdWQ2MTFcdWM4NzBcdWM4MDFcdWM3NzggXHVjZjU0XHViODA4XHVjMmE0XHVjZjU0IFx1Y2Y1OFx1YjNjNFx1YjI5NCBcdWM2ZDBcdWM3YTVcdWIyZDhcdWFlZDhcdWMxMWMgXHVkNTU5XHVjMGRkXHViNGU0XHVjNWQwXHVhYzhjIFx1Yzc3OFx1ZDEzMFx1YjEzNyBcdWMxMjBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWM4M1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNzdjXHViZDgwXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWIzYzhcdWM3NDQgXHVjNjk0XHVhZDZjXHVkNTU4XHVjNjAwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHViZDk5XHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWJhNzQgXHVjNTQ0XHViYjM0XHViMDk4IFx1YzExY1x1Yjg1YyBcdWM3NzhcdWQxMzBcdWIxMzcgXHVjMTIwXHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0LiBQKFAmbHQ7PTEwLDAwMClcdWFjMWNcdWM3NTggXHVjMzBkXHViOWNjXHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM3NzRcdWM1YjQgXHVjOWM4XHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCBcdWMxMWNcdWI4NWMgXHVjMTIwXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjMDBcdWFjYTlcdWM3NzQgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4xXHViYzg4XHVjNzQwIFx1YjJlNFx1ZDU4OVx1Yzc3NCBcdWM3NzhcdWQxMzBcdWIxMzcgXHVjMTFjXHViYzg0XHVjNjQwIFx1YmMxNFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0IFx1Yzc3OFx1ZDEzMFx1YjEzN1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuIFx1YzZiMFx1YjlhY1x1Yzc1OCBcdWJhYTlcdWQ0NWNcdWIyOTQgTlx1YmM4OCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWFjMDAgXHVjNzc4XHVkMTMwXHViMTM3XHVjNWQwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWIwOThcdWJhMzhcdWM5YzAgXHVjZWY0XHVkNGU4XHVkMTMwXHViMjk0IFx1YzVmMFx1YWNiMCBcdWI0MThcdWM3ODhcdWFjNzBcdWIwOTggXHVjNWYwXHVhY2IwIFx1YzU0OFx1YjQxOFx1YzViNFx1Yzc4OFx1YzViNFx1YjNjNCBcdWJiMzRcdWJjMjlcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWNmNTRcdWI4MDhcdWMyYTRcdWNmNTRcdWM1ZDBcdWMxMWNcdWIyOTQgS1x1YWMxY1x1Yzc1OCBcdWM3NzhcdWQxMzBcdWIxMzcgXHVjMTIwXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjI5NCBcdWFjZjVcdWM5ZGNcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTc0XHVjOGZjXHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjA5OFx1YmEzOFx1YzljMCBcdWM3NzhcdWQxMzBcdWIxMzcgXHVjMTIwXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjI5NCBcdWIwYThcdWM3NDAgXHVhYzgzIFx1YzkxMSBcdWM4MWNcdWM3N2MgXHVhYzAwXHVhY2E5XHVjNzc0IFx1YmU0NFx1YzJmYyBcdWFjODNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViOWNjIFx1YWMwMFx1YWNhOVx1Yzc0NCBcdWJjMWJcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM3NzRcdWI1NGMgXHVjNmQwXHVjN2E1XHVjMTIwXHVjMGRkXHViMmQ4XHVjNzc0IFx1YjBiNFx1YWM4YyBcdWI0MThcdWIyOTQgXHVjZDVjXHVjMThjXHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBOKDEgJmxlOyBOICZsZTsgMSwwMDApLCBcdWNmMDBcdWM3NzRcdWJlMTRcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4IFAoMSAmbGU7IFAgJmxlOyAxMCwwMDApLCBcdWFjZjVcdWM5ZGNcdWI4NWMgXHVjODFjXHVhY2Y1XHVkNTU4XHViMjk0IFx1Y2YwMFx1Yzc3NFx1YmUxNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMTggSygwICZsZTsgSyAmbHQ7IE4pXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFBcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2YwMFx1Yzc3NFx1YmUxNFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViNDUwIFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVhZGY4IFx1YWMwMFx1YWNhOVx1Yzc3NCBcdWNjMjhcdWI4NDBcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBcdWFjMDBcdWFjYTlcdWM3NDAgMSBcdWM3NzRcdWMwYzEgMSwwMDAsMDAwIFx1Yzc3NFx1ZDU1OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjhcdWM5MDRcdWM1ZDAgXHVjNmQwXHVjN2E1XHVjMTIwXHVjMGRkXHViMmQ4XHVjNzc0IFx1YjBiNFx1YWM4YyBcdWI0MThcdWIyOTQgXHVjZDVjXHVjMThjXHVjNzU4IFx1YjNjOFx1YzY0MCBcdWI5Y2NcdWM1N2QgMVx1YmM4OFx1YWNmYyBOXHViYzg4IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yjk3YyBcdWM3ODdcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNSBcdWQ1NThcdWIyZTRcdWJhNzQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD4xLTMgMy0yIDItNVx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVjNzc4XHVkMTMwXHViMTM3XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWFkZjggXHVhYzAwXHVhY2E5XHViNGU0XHVjNzQwIDQgMyA5XHVjNmQwXHVjNzc0IFx1YjA5OFx1YzYyNFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWNmNTRcdWI4MDhcdWMyYTRcdWNmNTRcdWM1ZDBcdWMxMWMgMVx1YWMxY1x1Yzc1OCBcdWNmMDBcdWM3NzRcdWJlMTRcdWM3NDAgXHViYjM0XHVjMGMxXHVjNzNjXHViODVjIFx1YzhmY1x1YjJjOFx1YWU0YyA5XHVjNmQwXHVjOWRjXHViOWFjXHViOTdjIFx1YmU4MCBcdWFjODMgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzAwXHVhY2E5XHVjNzQwIDRcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTgwMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRlbGVwaG9uZSBMaW5lcyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gd2FudHMgdG8gc2V0IHVwIGEgdGVsZXBob25lIGxpbmUgYXQgaGlzIGZhcm0uIFVuZm9ydHVuYXRlbHksIHRoZSBwaG9uZSBjb21wYW55IGlzIHVuY29vcGVyYXRpdmUsIHNvIGhlIG5lZWRzIHRvIHBheSBmb3Igc29tZSBvZiB0aGUgY2FibGVzIHJlcXVpcmVkIHRvIGNvbm5lY3QgaGlzIGZhcm0gdG8gdGhlIHBob25lIHN5c3RlbS48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIE4gKDEgJmx0Oz0gTiAmbHQ7PSAxLDAwMCkgZm9ybG9ybiB0ZWxlcGhvbmUgcG9sZXMgY29udmVuaWVudGx5IG51bWJlcmVkIDEuLk4gdGhhdCBhcmUgc2NhdHRlcmVkIGFyb3VuZCBGYXJtZXIgSm9obiYjMzk7cyBwcm9wZXJ0eTsgbm8gY2FibGVzIGNvbm5lY3QgYW55IHRoZW0uICZuYnNwO0EgdG90YWwgb2YgUCAoMSAmbHQ7PSBQICZsdDs9IDEwLDAwMCkgcGFpcnMgb2YgcG9sZXMgY2FuIGJlIGNvbm5lY3RlZCBieSBhIGNhYmxlOyB0aGUgcmVzdCBhcmUgdG9vIGZhciBhcGFydC48XC9wPlxyXG5cclxuPHA+VGhlIGktdGggY2FibGUgY2FuIGNvbm5lY3QgdGhlIHR3byBkaXN0aW5jdCBwb2xlcyBBX2kgYW5kIEJfaSwgd2l0aCBsZW5ndGggTF9pICgxICZsdDs9IExfaSAmbHQ7PSAxLDAwMCwwMDApIHVuaXRzIGlmIHVzZWQuIFRoZSBpbnB1dCBkYXRhIHNldCBuZXZlciBuYW1lcyBhbnkge0FfaSxCX2l9IHBhaXIgbW9yZSB0aGFuIG9uY2UuIFBvbGUgMSBpcyBhbHJlYWR5IGNvbm5lY3RlZCB0byB0aGUgcGhvbmUgc3lzdGVtLCBhbmQgcG9sZSBOIGlzIGF0IHRoZSBmYXJtLiBQb2xlcyAxIGFuZCBOIG5lZWQgdG8gYmUgY29ubmVjdGVkIGJ5IGEgcGF0aCBvZiBjYWJsZXM7IHRoZSByZXN0IG9mIHRoZSBwb2xlcyBtaWdodCBiZSB1c2VkIG9yIG1pZ2h0IG5vdCBiZSB1c2VkLjxcL3A+XHJcblxyXG48cD5BcyBpdCB0dXJucyBvdXQsIHRoZSBwaG9uZSBjb21wYW55IGlzIHdpbGxpbmcgdG8gcHJvdmlkZSBGYXJtZXIgSm9obiB3aXRoIEsgKDAgJmx0Oz0gSyAmbHQ7IE4pIGxlbmd0aHMgb2YgY2FibGUgZm9yIGZyZWUuIEJleW9uZCB0aGF0IGhlIHdpbGwgaGF2ZSB0byBwYXkgYSBwcmljZSBlcXVhbCB0byB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHJlbWFpbmluZyBjYWJsZSBoZSByZXF1aXJlcyAoZWFjaCBwYWlyIG9mIHBvbGVzIGlzIGNvbm5lY3RlZCB3aXRoIGEgc2VwYXJhdGUgY2FibGUpLCBvciAwIGlmIGhlIGRvZXMgbm90IG5lZWQgYW55IGFkZGl0aW9uYWwgY2FibGVzLjxcL3A+XHJcblxyXG48cD5EZXRlcm1pbmUgdGhlIG1pbmltdW0gYW1vdW50IHRoYXQgRmFybWVyIEpvaG4gbXVzdCBwYXkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOLCBQLCBhbmQgSzxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLlArMTogTGluZSBpKzEgY29udGFpbnMgdGhlIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogQV9pLCBCX2ksIGFuZCBMX2k8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogQSBzaW5nbGUgaW50ZWdlciwgdGhlIG1pbmltdW0gYW1vdW50IEZhcm1lciBKb2huIGNhbiBwYXkuIElmIGl0IGlzIGltcG9zc2libGUgdG8gY29ubmVjdCB0aGUgZmFybSB0byB0aGUgcGhvbmUgY29tcGFueSwgcHJpbnQgLTEuPFwvcD5cclxuIiwiaGludCI6IjxwPklmIHBvbGUgMSBpcyBjb25uZWN0ZWQgdG8gcG9sZSAzLCBwb2xlIDMgdG8gcG9sZSAyLCBhbmQgcG9sZSAyIHRvIHBvbGUgNSB0aGVuIEZhcm1lciBKb2huIHJlcXVpcmVzIGNhYmxlcyBvZiBsZW5ndGggNCwgMywgYW5kIDkuIFRoZSBwaG9uZSBjb21wYW55IHdpbGwgcHJvdmlkZSB0aGUgY2FibGUgb2YgbGVuZ3RoIDksIHNvIHRoZSBsb25nZXN0IGNhYmxlIG5lZWRlZCBoYXMgbGVuZ3RoIDQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO January 2008 Contest > Silver 3번