시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 219 81 60 33.898%

문제

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

각각의 학생들의 번호가 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+XHJcblxyXG48cD4xXHViYzg4XHVjNzQwIFx1YjJlNFx1ZDU4OVx1Yzc3NCBcdWM3NzhcdWQxMzBcdWIxMzcgXHVjMTFjXHViYzg0XHVjNjQwIFx1YmMxNFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0IFx1Yzc3OFx1ZDEzMFx1YjEzN1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuIFx1YzZiMFx1YjlhY1x1Yzc1OCBcdWJhYTlcdWQ0NWNcdWIyOTQgTlx1YmM4OCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWFjMDAgXHVjNzc4XHVkMTMwXHViMTM3XHVjNWQwIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjA5OFx1YmEzOFx1YzljMCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWIyOTQgXHVjNWYwXHVhY2IwIFx1YjQxOFx1YzViNCBcdWM3ODhcdWFjNzBcdWIwOTggXHVjNWYwXHVhY2IwIFx1YzU0OFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWIzYzQgXHViYjM0XHViYzI5XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHVjZjU0XHViODA4XHVjMmE0XHVjZjU0XHVjNWQwXHVjMTFjXHViMjk0IEtcdWFjMWNcdWM3NTggXHVjNzc4XHVkMTMwXHViMTM3IFx1YzEyMFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgXHVhY2Y1XHVjOWRjXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU3NFx1YzhmY1x1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIwOThcdWJhMzhcdWM5YzAgXHVjNzc4XHVkMTMwXHViMTM3IFx1YzEyMFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgXHViMGE4XHVjNzQwIFx1YWM4MyBcdWM5MTEgXHVjODFjXHVjNzdjIFx1YWMwMFx1YWNhOVx1Yzc3NCBcdWJlNDRcdWMyZmMgXHVhYzgzXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjljYyBcdWFjMDBcdWFjYTlcdWM3NDQgXHViYzFiXHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVjNzc0XHViNTRjIFx1YzZkMFx1YzdhNVx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc3NCBcdWIwYjRcdWFjOGMgXHViNDE4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgTigxICZsZTsgTiAmbGU7IDEsMDAwKSwgXHVjZjAwXHVjNzc0XHViZTE0XHVjMTIwXHVjNzU4IFx1YWMxY1x1YzIxOCBQKDEgJmxlOyBQICZsZTsgMTAsMDAwKSwgXHVhY2Y1XHVjOWRjXHViODVjIFx1YzgxY1x1YWNmNVx1ZDU1OFx1YjI5NCBcdWNmMDBcdWM3NzRcdWJlMTRcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4IEsoMCAmbGU7IEsgJmx0OyBOKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBQXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNmMDBcdWM3NzRcdWJlMTRcdWM3NzQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWNlZjRcdWQ0ZThcdWQxMzAgXHViYzg4XHVkNjM4XHVjNjQwIFx1YWRmOCBcdWFjMDBcdWFjYTlcdWM3NzQgXHVjYzI4XHViODQwXHViODVjIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC4gXHVhYzAwXHVhY2E5XHVjNzQwIDEgXHVjNzc0XHVjMGMxIDEsMDAwLDAwMCBcdWM3NzRcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2ZDBcdWM3YTVcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NzQgXHViMGI0XHVhYzhjIFx1YjQxOFx1YjI5NCBcdWNkNWNcdWMxOGNcdWM3NTggXHViM2M4XHVjNjQwIFx1YjljY1x1YzU3ZCAxXHViYzg4XHVhY2ZjIE5cdWJjODggXHVjZWY0XHVkNGU4XHVkMTMwXHViOTdjIFx1Yzc4N1x1YjI5NCBcdWFjODNcdWM3NzQgXHViZDg4XHVhYzAwXHViMmE1IFx1ZDU1OFx1YjJlNFx1YmE3NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPjEtMyAzLTIgMi01XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWM3NzhcdWQxMzBcdWIxMzdcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTVjXHViMmU0XHViYTc0IFx1YWRmOCBcdWFjMDBcdWFjYTlcdWI0ZTRcdWM3NDAgNCAzIDlcdWM2ZDBcdWM3NzQgXHViMDk4XHVjNjI0XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1Y2Y1NFx1YjgwOFx1YzJhNFx1Y2Y1NFx1YzVkMFx1YzExYyAxXHVhYzFjXHVjNzU4IFx1Y2YwMFx1Yzc3NFx1YmUxNFx1Yzc0MCBcdWJiMzRcdWMwYzFcdWM3M2NcdWI4NWMgXHVjOGZjXHViMmM4XHVhZTRjIDlcdWM2ZDBcdWM5ZGNcdWI5YWNcdWI5N2MgXHViZTgwIFx1YWM4MyBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMDBcdWFjYTlcdWM3NDAgNFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxODAwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGVsZXBob25lIExpbmVzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiB3YW50cyB0byBzZXQgdXAgYSB0ZWxlcGhvbmUgbGluZSBhdCBoaXMgZmFybS4gVW5mb3J0dW5hdGVseSwgdGhlIHBob25lIGNvbXBhbnkgaXMgdW5jb29wZXJhdGl2ZSwgc28gaGUgbmVlZHMgdG8gcGF5IGZvciBzb21lIG9mIHRoZSBjYWJsZXMgcmVxdWlyZWQgdG8gY29ubmVjdCBoaXMgZmFybSB0byB0aGUgcGhvbmUgc3lzdGVtLjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgTiAoMSAmbHQ7PSBOICZsdDs9IDEsMDAwKSBmb3Jsb3JuIHRlbGVwaG9uZSBwb2xlcyBjb252ZW5pZW50bHkgbnVtYmVyZWQgMS4uTiB0aGF0IGFyZSBzY2F0dGVyZWQgYXJvdW5kIEZhcm1lciBKb2huJiMzOTtzIHByb3BlcnR5OyBubyBjYWJsZXMgY29ubmVjdCBhbnkgdGhlbS4gJm5ic3A7QSB0b3RhbCBvZiBQICgxICZsdDs9IFAgJmx0Oz0gMTAsMDAwKSBwYWlycyBvZiBwb2xlcyBjYW4gYmUgY29ubmVjdGVkIGJ5IGEgY2FibGU7IHRoZSByZXN0IGFyZSB0b28gZmFyIGFwYXJ0LjxcL3A+XHJcblxyXG48cD5UaGUgaS10aCBjYWJsZSBjYW4gY29ubmVjdCB0aGUgdHdvIGRpc3RpbmN0IHBvbGVzIEFfaSBhbmQgQl9pLCB3aXRoIGxlbmd0aCBMX2kgKDEgJmx0Oz0gTF9pICZsdDs9IDEsMDAwLDAwMCkgdW5pdHMgaWYgdXNlZC4gVGhlIGlucHV0IGRhdGEgc2V0IG5ldmVyIG5hbWVzIGFueSB7QV9pLEJfaX0gcGFpciBtb3JlIHRoYW4gb25jZS4gUG9sZSAxIGlzIGFscmVhZHkgY29ubmVjdGVkIHRvIHRoZSBwaG9uZSBzeXN0ZW0sIGFuZCBwb2xlIE4gaXMgYXQgdGhlIGZhcm0uIFBvbGVzIDEgYW5kIE4gbmVlZCB0byBiZSBjb25uZWN0ZWQgYnkgYSBwYXRoIG9mIGNhYmxlczsgdGhlIHJlc3Qgb2YgdGhlIHBvbGVzIG1pZ2h0IGJlIHVzZWQgb3IgbWlnaHQgbm90IGJlIHVzZWQuPFwvcD5cclxuXHJcbjxwPkFzIGl0IHR1cm5zIG91dCwgdGhlIHBob25lIGNvbXBhbnkgaXMgd2lsbGluZyB0byBwcm92aWRlIEZhcm1lciBKb2huIHdpdGggSyAoMCAmbHQ7PSBLICZsdDsgTikgbGVuZ3RocyBvZiBjYWJsZSBmb3IgZnJlZS4gQmV5b25kIHRoYXQgaGUgd2lsbCBoYXZlIHRvIHBheSBhIHByaWNlIGVxdWFsIHRvIHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3QgcmVtYWluaW5nIGNhYmxlIGhlIHJlcXVpcmVzIChlYWNoIHBhaXIgb2YgcG9sZXMgaXMgY29ubmVjdGVkIHdpdGggYSBzZXBhcmF0ZSBjYWJsZSksIG9yIDAgaWYgaGUgZG9lcyBub3QgbmVlZCBhbnkgYWRkaXRpb25hbCBjYWJsZXMuPFwvcD5cclxuXHJcbjxwPkRldGVybWluZSB0aGUgbWluaW11bSBhbW91bnQgdGhhdCBGYXJtZXIgSm9obiBtdXN0IHBheS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4sIFAsIGFuZCBLPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uUCsxOiBMaW5lIGkrMSBjb250YWlucyB0aGUgdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBBX2ksIEJfaSwgYW5kIExfaTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyLCB0aGUgbWluaW11bSBhbW91bnQgRmFybWVyIEpvaG4gY2FuIHBheS4gSWYgaXQgaXMgaW1wb3NzaWJsZSB0byBjb25uZWN0IHRoZSBmYXJtIHRvIHRoZSBwaG9uZSBjb21wYW55LCBwcmludCAtMS48XC9wPlxyXG4iLCJoaW50IjoiPHA+SWYgcG9sZSAxIGlzIGNvbm5lY3RlZCB0byBwb2xlIDMsIHBvbGUgMyB0byBwb2xlIDIsIGFuZCBwb2xlIDIgdG8gcG9sZSA1IHRoZW4gRmFybWVyIEpvaG4gcmVxdWlyZXMgY2FibGVzIG9mIGxlbmd0aCA0LCAzLCBhbmQgOS4gVGhlIHBob25lIGNvbXBhbnkgd2lsbCBwcm92aWRlIHRoZSBjYWJsZSBvZiBsZW5ndGggOSwgc28gdGhlIGxvbmdlc3QgY2FibGUgbmVlZGVkIGhhcyBsZW5ndGggNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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