농부 존의 어려움 중의 하나는 매일 소들이 이상이 없는지를 점검하는 일이다.

길은 1 에서 M (1 <= M <= 50,000)까지 번호가 부여되어 있고 1 번 목초지에서 N 번 목초지로 길이 있다(주어진 입력에서는 1 번 목초지에서 N 번 목초지로 연결되어 있다)

1 에서 N (1 <= N <= 10,000)까지 번호가 매겨진 목초지는 양방향 길로 연결되어 있다.

i 번 째 길은 목초지 P1_i 와 P2_i (1 <= P1_i <= N; 1 <= P2_i <= N)에 연결되어 있고 Ti (1 <= T_i <= 1,000,000)만큼의 시간이 소요된다.

그는 이 길 중 몇 길을 개선하려고 한다.

특별히 , 그는 K (1 <= K <= 20)개의 길을 선택해서 이 길을 고속도로로 만들어 이동시간을 0 으로 만들려고 한다.

존을 도와 목초지 1 에서 N 까지 가는 최소 시간을 찾아라.

입력

• 첫 줄은 세 정수 N,M,K 가 주어진다
• i+1 번 째 줄은 길 i 의 P1_i, P2_i, and T_i 가 정수로 주어진다.

출력

입출력 예

입력

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

출력

1

출처:usaco FEB 2009 gold