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

문제

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

각각의 학생들의 번호가 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+XHVjY2FiXHVjOWY4XHVjOTA0XHVjNWQwIFx1YzZkMFx1YzdhNVx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc3NCBcdWIwYjRcdWFjOGMgXHViNDE4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWIzYzhcdWM2NDAgXHViOWNjXHVjNTdkIDFcdWJjODhcdWFjZmMgTlx1YmM4OCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5N2MgXHVjNzg3XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJkODhcdWFjMDBcdWIyYTUgXHVkNTU4XHViMmU0XHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+MS0zIDMtMiAyLTVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1Yzc3OFx1ZDEzMFx1YjEzN1x1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTRcdWJhNzQgXHVhZGY4IFx1YWMwMFx1YWNhOVx1YjRlNFx1Yzc0MCA0IDMgOVx1YzZkMFx1Yzc3NCBcdWIwOThcdWM2MjRcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHVjZjU0XHViODA4XHVjMmE0XHVjZjU0XHVjNWQwXHVjMTFjIDFcdWFjMWNcdWM3NTggXHVjZjAwXHVjNzc0XHViZTE0XHVjNzQwIFx1YmIzNFx1YzBjMVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWIyYzhcdWFlNGMgOVx1YzZkMFx1YzlkY1x1YjlhY1x1Yjk3YyBcdWJlODAgXHVhYzgzIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMwMFx1YWNhOVx1Yzc0MCA0XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4MDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUZWxlcGhvbmUgTGluZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIHdhbnRzIHRvIHNldCB1cCBhIHRlbGVwaG9uZSBsaW5lIGF0IGhpcyBmYXJtLiBVbmZvcnR1bmF0ZWx5LCB0aGUgcGhvbmUgY29tcGFueSBpcyB1bmNvb3BlcmF0aXZlLCBzbyBoZSBuZWVkcyB0byBwYXkgZm9yIHNvbWUgb2YgdGhlIGNhYmxlcyByZXF1aXJlZCB0byBjb25uZWN0IGhpcyBmYXJtIHRvIHRoZSBwaG9uZSBzeXN0ZW0uPFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBOICgxICZsdDs9IE4gJmx0Oz0gMSwwMDApIGZvcmxvcm4gdGVsZXBob25lIHBvbGVzIGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5OIHRoYXQgYXJlIHNjYXR0ZXJlZCBhcm91bmQgRmFybWVyIEpvaG4mIzM5O3MgcHJvcGVydHk7IG5vIGNhYmxlcyBjb25uZWN0IGFueSB0aGVtLiAmbmJzcDtBIHRvdGFsIG9mIFAgKDEgJmx0Oz0gUCAmbHQ7PSAxMCwwMDApIHBhaXJzIG9mIHBvbGVzIGNhbiBiZSBjb25uZWN0ZWQgYnkgYSBjYWJsZTsgdGhlIHJlc3QgYXJlIHRvbyBmYXIgYXBhcnQuPFwvcD5cclxuXHJcbjxwPlRoZSBpLXRoIGNhYmxlIGNhbiBjb25uZWN0IHRoZSB0d28gZGlzdGluY3QgcG9sZXMgQV9pIGFuZCBCX2ksIHdpdGggbGVuZ3RoIExfaSAoMSAmbHQ7PSBMX2kgJmx0Oz0gMSwwMDAsMDAwKSB1bml0cyBpZiB1c2VkLiBUaGUgaW5wdXQgZGF0YSBzZXQgbmV2ZXIgbmFtZXMgYW55IHtBX2ksQl9pfSBwYWlyIG1vcmUgdGhhbiBvbmNlLiBQb2xlIDEgaXMgYWxyZWFkeSBjb25uZWN0ZWQgdG8gdGhlIHBob25lIHN5c3RlbSwgYW5kIHBvbGUgTiBpcyBhdCB0aGUgZmFybS4gUG9sZXMgMSBhbmQgTiBuZWVkIHRvIGJlIGNvbm5lY3RlZCBieSBhIHBhdGggb2YgY2FibGVzOyB0aGUgcmVzdCBvZiB0aGUgcG9sZXMgbWlnaHQgYmUgdXNlZCBvciBtaWdodCBub3QgYmUgdXNlZC48XC9wPlxyXG5cclxuPHA+QXMgaXQgdHVybnMgb3V0LCB0aGUgcGhvbmUgY29tcGFueSBpcyB3aWxsaW5nIHRvIHByb3ZpZGUgRmFybWVyIEpvaG4gd2l0aCBLICgwICZsdDs9IEsgJmx0OyBOKSBsZW5ndGhzIG9mIGNhYmxlIGZvciBmcmVlLiBCZXlvbmQgdGhhdCBoZSB3aWxsIGhhdmUgdG8gcGF5IGEgcHJpY2UgZXF1YWwgdG8gdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCByZW1haW5pbmcgY2FibGUgaGUgcmVxdWlyZXMgKGVhY2ggcGFpciBvZiBwb2xlcyBpcyBjb25uZWN0ZWQgd2l0aCBhIHNlcGFyYXRlIGNhYmxlKSwgb3IgMCBpZiBoZSBkb2VzIG5vdCBuZWVkIGFueSBhZGRpdGlvbmFsIGNhYmxlcy48XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSBtaW5pbXVtIGFtb3VudCB0aGF0IEZhcm1lciBKb2huIG11c3QgcGF5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiwgUCwgYW5kIEs8XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi5QKzE6IExpbmUgaSsxIGNvbnRhaW5zIHRoZSB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IEFfaSwgQl9pLCBhbmQgTF9pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IEEgc2luZ2xlIGludGVnZXIsIHRoZSBtaW5pbXVtIGFtb3VudCBGYXJtZXIgSm9obiBjYW4gcGF5LiBJZiBpdCBpcyBpbXBvc3NpYmxlIHRvIGNvbm5lY3QgdGhlIGZhcm0gdG8gdGhlIHBob25lIGNvbXBhbnksIHByaW50IC0xLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JZiBwb2xlIDEgaXMgY29ubmVjdGVkIHRvIHBvbGUgMywgcG9sZSAzIHRvIHBvbGUgMiwgYW5kIHBvbGUgMiB0byBwb2xlIDUgdGhlbiBGYXJtZXIgSm9obiByZXF1aXJlcyBjYWJsZXMgb2YgbGVuZ3RoIDQsIDMsIGFuZCA5LiBUaGUgcGhvbmUgY29tcGFueSB3aWxsIHByb3ZpZGUgdGhlIGNhYmxlIG9mIGxlbmd0aCA5LCBzbyB0aGUgbG9uZ2VzdCBjYWJsZSBuZWVkZWQgaGFzIGxlbmd0aCA0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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