Farmer John은 매일 성실하게 소들을 살핍니다. $1,\ldots,M$로 번호가 붙은 $M$개 $(1 \le M \le 50,000)$의 길 중 일부를 따라 목초지 $1$에서 목초지 $N$까지 갑니다(테스트 데이터의 길 지도에서는 이 이동이 항상 가능합니다). Farmer John의 농장에 있는 $N$개 $(1 \le N \le 10,000)$의 목초지는 $1,\ldots,N$로 번호가 붙어 있으며 현재 양방향 흙길로 연결되어 있습니다. 각 길 $i$는 목초지 $P1_{i}$와 $P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$를 연결하고, 지나가는 데 $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ 시간 단위가 걸립니다.

긴 이동 시간을 절약하기 위해 농장의 길 일부를 정비하려고 합니다. 구체적으로 $K$개 $(1 \le K \le 20)$의 길을 선택해 간선도로로 바꾸며, 이로써 각 길을 지나는 시간을 사실상 $0$으로 줄입니다. 목초지 $1$에서 $N$까지 걸리는 시간이 최소가 되도록 어떤 길을 정비할지 FJ를 도와주세요.

입력

• 1번째 줄: 공백으로 구분된 세 정수 $N$, $M$, $K$.

• $2,\ldots,M+1$번째 줄: $i+1$번째 줄은 공백으로 구분된 세 정수 $P1_{i}$, $P2_{i}$, $T_{i}$로 길 $i$를 설명합니다.

출력

• 1번째 줄: $K$개 이하의 간선을 정비한 뒤의 최단 경로 길이.

예제

입력 1

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

출력 1

1

참고

$K$는 $1$입니다. 길 $3->4$를 정비하여 걸리는 시간을 $100$에서 $0$으로 줄입니다. 새로운 최단 경로는 $1->3->4$이며 총 소요 시간은 이제 $1$입니다.

문제 작성: Percy Liang, 2008년