고속도로 공사

매일 A도시에서 B도시까지 출퇴근하는 상황에서, 최대 K개의 도로를 공사하여 통과 시간을 0으로 만들 수 있다. 공사는 이미 존재하는 도로에만 가능하다.

N개의 도시와 M개의 양방향 도로, 각 도로의 통과 시간이 주어질 때, 최대 K개 이하의 도로를 공사하여 1번 도시에서 N번 도시까지 가는 최소 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 50,000, 1 ≤ K ≤ 20) 다음 M개의 줄에 각 도로가 연결하는 두 도시와 통과 시간이 주어진다. 시간은 1,000,000 이하의 자연수이다.

출력

최소 이동 시간을 출력한다.

입출력 예시

입력 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

출력 1

1