1397: 도로포장

상우는 매일 서울에서 김해까지 출퇴근을 한다. 하지만 잠이 많은 상우는 늦잠을 자 김해에 늦게 도착하기 일쑤다. 돈이 많은 상우는 고민 끝에 K개의 도로를 포장하여 서울에서 김해까지 가는 시간을 단축하려 한다. 만약 어떤 도로를 포장하게 되면 그 도로를 이동하는데 시간이 걸리지 않게 된다.
문제는 N개의 도시가 주어지고 그 사이 도로들과 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 여기서 도로를 포장하게 되면 도로를 지나는데 걸리는 시간이 0이라 하자. 또한 편의상 서울은 1번 도시, 김해는 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이다.

첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.