Farmer John controlla diligentemente le mucche ogni giorno. Percorre alcuni degli $M$ $(1 \le M \le 50,000)$ sentieri, numerati $1,\ldots,M$, dal pascolo $1$ fino al pascolo $N$ (un viaggio sempre possibile nelle mappe dei sentieri dei dati di test). Gli $N$ $(1 \le N \le 10,000)$ pascoli della fattoria di Farmer John, numerati $1,\ldots,N$, sono attualmente collegati da sentieri sterrati bidirezionali. Ogni sentiero $i$ collega i pascoli $P1_{i}$ e $P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$ e richiede $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ unità di tempo per essere percorso.

Vuole rinnovare alcuni sentieri della fattoria per risparmiare tempo nel suo lungo viaggio. In particolare, sceglierà $K$ $(1 \le K \le 20)$ sentieri da trasformare in strade principali, riducendo di fatto il loro tempo di percorrenza a $0$. Aiuta FJ a scegliere quali sentieri rinnovare per minimizzare il tempo necessario per andare dal pascolo $1$ al $N$.

Input

• Riga 1: tre interi separati da spazi: $N$, $M$ e $K$.

• Righe $2,\ldots,M+1$: la riga $i+1$ descrive il sentiero $i$ con tre interi separati da spazi: $P1_{i}$, $P2_{i}$ e $T_{i}$.

Output

• Riga 1: la lunghezza del cammino più breve dopo aver rinnovato al massimo $K$ archi.

Esempi

Input 1

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

Output 1

1

Nota

$K$ è $1$; rinnova il sentiero $3->4$ affinché richieda $0$ anziché $100$. Il nuovo cammino più breve è $1->3->4$, e il tempo totale di percorrenza ora è $1$.

Autore del problema: Percy Liang, 2008