Ispirato dal nuovo parco acquatico a Machu Picchu in Perù, Farmer John ne costruisce uno per le mucche. La maggiore attrazione sarà un enorme scivolo di progetto particolare.

Comprende $E$ ($1 \le E \le 150,000$) piccoli scivoli tra $V$ ($2 \le V \le 50,000$) piscine $1..V$. Ogni scivolo è percorribile solo nel verso corretto. Le mucche partono da 1 e arrivano all’ultima $V$. Ogni piscina eccetto 1 ha almeno uno scivolo entrante; eccetto $V$, almeno un altro uscente.

Da ogni piscina si raggiunge la fine $V$. Non si può uscire da una e ritornarvi dopo alcuni scivoli.

Lo scivolo $i$ va da $P_{i}$ a $Q_{i}$ ($1 \le P_{i} \le V; 1 \le Q_{i} \le V; P_{i} \ne Q_{i}$), con divertimento $F_{i}$ ($0 \le F_{i} \le 2,000,000,000$). Bessie somma i valori di tutti gli scivoli percorsi.

Dopo tanta coda vuole il massimo. Sceglie normalmente le uscite, ma perde il controllo al massimo $K$ volte ($1 \le K \le 10$) e prende un’uscita casuale, anche in 1.

Quanto divertimento garantisce scegliendo per massimizzare il caso peggiore?

Esempio: 3 piscine, numeri fra parentesi quadre, 4 scivoli e $K$ uguale a 1; divertimento fuori dalle parentesi:

          [1]
         /   \
   5 -> /     \ <- 9
       /       \
     [2]---3---[3]
        \__5__/

Va sempre da 1 a 3. Liberamente sceglierebbe 1 a 2 e poi lo scivolo da 5 a 3: $5+5=10$. Perdere il controllo in 1 può portare direttamente a 3 con 9; in 2 solo $5+3 = 8$.

Sceglie $1\to3$ per 9. Se perde il controllo in 1 e prende $1\to2$, non lo perderà in 2 e otterrà 10. Garantisce almeno 9.

Input

• Riga $1$: interi $V$, $E$, $K$ separati da spazi.
• Righe $2..E + 1$: la riga $i+1$ contiene interi $P_{i}$, $Q_{i}$, $F_{i}$ separati da spazi.

Output

• Riga $1$: un intero, il divertimento minimo garantito da Bessie.

Esempi

Input 1

3 4 1
2 3 5
1 2 5
1 3 9
2 3 3

Output 1

9

Autore del problema: John Pardon, 2010