문제
2014년 6월 4일 지방선거에서 인천시장에 출마한 유영현 후보는 세월호 참사와 같은 해양사고를 방지하기 위해 인천에서 가장 많은 배가 운항되는 덕적도까지 해저터널을 만들겠다는 공약을 내걸어 시장에 당선이 되었다. 하지만 육지에서 덕적도까지 한 번에 연결할 수 있는 해저터널은 수심이 너무 깊은 구간 때문에 불가능하다는 진단이 나왔다.
따라서 여러 섬들을 연결하는 해저터널을 건설하고 수심이 깊은 일부 구간은 다리를 놓아 연결하는 방법을 모색하게 되었다.
다행스럽게도 인천아시안게임을 유치하면서 중앙정부로부터 인천지역의 섬들을 연결하는 다리를 K개까지 건설하는 비용을 지원받기로 하였다.
섬 사이에는 조류나 수심 등의 영향 때문에 다리나 해양터널의 건설이 아예 불가능한 곳도 많다.
문제의 편의를 위해 육지도 한 개의 섬이라고 가정을 하자.
두 섬 사이에 해양터널을 건설하는데 드는 비용은 그 섬 사이의 최대수심에 따라 결정이 된다.
그렇다면 육지에서 덕적도까지 연결하기 위해 수심이 가장 깊은 K개의 구간은 정부의 지원으로 다리를 건설하기로 하고 나머지 구간에서 수심이 가장 깊은 구간을 찾아 해저터널을 건설하기 위한 예산을 편성하려고 한다. 예를 들어 육지를 1 덕적도를 4, K가 1이라 하고 1-2-3-4를 연결하려고 할 때, 각 구간의 최대 수심이 2, 10, 5라고 하면,
수심이 10인 2-3구간은 다리를 건설하고 해양터널을 건설하는 구간의 최대 수심은 3-4사이의 5가 된다.
이 때 수심이 가장 깊은 구간의 수심이 최소가 되도록 경로를 구성해야 예산을 절감할 수 있다.
해양터널 또는 다리의 건설이 가능한 섬과 섬 사이의 최대 수심이 주어질 때 해양터널을 건설할 구간 중 최대 수심이 최소가 되도록 경로를 구성하여 그 값을 출력하는 프로그램을 작성하라.
입력
첫 줄에 육지와 덕적도를 포함한 섬의 개수 N(1 ≤ N ≤ 1 000)과 건설 가능한 구간의 개수 P(1 ≤ P ≤ 10 000) 그리고 정부로부터 비용을 지원받기로 한 다리의 개수인 K(0 ≤ K < N)가 주어진다.
둘째 줄부터 P개의 줄에는 각각 세 개의 정수가 주어지는데 건설 가능한 구간에 대한 정보이다.
첫 번째와 두 번째는 섬의 번호이고 세 번째는 그 두 섬 사이의 최대 수심 Ci (1 ≤ Ci ≤ 1 000 000)이다.
섬의 번호 중 1번은 육지이며 N번은 덕적도이다.
출력
예제
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
4
로그인해야 코드를 작성할 수 있어요.