Farmer John vuole installare una linea telefonica nella sua fattoria. Purtroppo la compagnia telefonica non è collaborativa, quindi deve pagare alcuni dei cavi necessari per collegare la fattoria alla rete.

Ci sono $N$ pali telefonici isolati, $(1 \le N \le 1,000)$, sparsi nella sua proprietà e comodamente numerati $1..N$; nessun cavo li collega. In totale $P$ coppie di pali, $(1 \le P \le 10,000)$, possono essere collegate con un cavo; le altre sono troppo lontane.

Il cavo $i$ può collegare i due pali distinti $A_i$ e $B_i$ e, se utilizzato, ha lunghezza $L_i$ unità, $(1 \le L_i \le 1,000,000)$. I dati non indicano mai una coppia {$A_i,B_i$} più di una volta. Il palo $1$ è già collegato alla rete, e il palo $N$ si trova nella fattoria. I pali $1$ e $N$ devono essere collegati da un percorso di cavi; gli altri pali possono essere usati oppure no.

La compagnia è disposta a fornire gratuitamente $K$ cavi a Farmer John, $(0 \le K < N)$. Per il resto dovrà pagare un prezzo pari alla lunghezza del più lungo cavo ancora necessario (ogni coppia di pali è collegata con un cavo separato), oppure $0$ se non servono altri cavi.

Determina la somma minima che Farmer John deve pagare.

Input

Leggi i dati dall’input standard.

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

• Righe $2..P+1$: la riga $i+1$ contiene tre interi separati da spazi: $A_i$, $B_i$ e $L_i$.

Output

Scrivi la risposta sull’output standard.

• Riga 1: un intero, la somma minima che Farmer John può pagare. Se è impossibile collegare la fattoria alla compagnia, stampa $-1$.

Esempi

Input 1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

Output 1

4

Nota

Ci sono 5 pali. Il palo $1$ non può essere collegato direttamente ai pali $4$ o $5$. Il palo $5$ non può essere collegato direttamente ai pali $1$ o $3$. Tutte le altre coppie possono essere collegate. La compagnia fornirà un cavo gratuito.

Se il palo $1$ è collegato al $3$, il $3$ al $2$ e il $2$ al $5$, Farmer John richiede cavi di lunghezze $4$, $3$ e $9$. La compagnia fornirà il cavo di lunghezza $9$, quindi il più lungo cavo ancora necessario ha lunghezza $4$.

Autore del problema: Paul Christiano, 2007