Inspirado pelo novo parque aquático em Machu Picchu, Peru, Farmer John decide construir um para as vacas. A maior atração será um enorme escorrega de desenho peculiar.

Tem $E$ ($1 \le E \le 150,000$) pequenos escorregas entre $V$ ($2 \le V \le 50,000$) piscinas $1..V$. São percorridos só no sentido correto. As vacas começam em 1 e terminam em $V$. Cada piscina exceto 1 tem pelo menos um a entrar; exceto $V$, pelo menos outro a sair.

De qualquer piscina pode chegar-se ao fim $V$. Não é possível sair de uma e regressar após percorrer escorregas.

O escorrega $i$ vai de $P_{i}$ a $Q_{i}$ ($1 \le P_{i} \le V; 1 \le Q_{i} \le V; P_{i} \ne Q_{i}$), com diversão $F_{i}$ ($0 \le F_{i} \le 2,000,000,000$). A diversão total de Bessie é a soma dos valores percorridos.

Depois de longa espera na fila, quer o máximo. Geralmente escolhe as saídas, mas perde o controlo no máximo $K$ vezes ($1 \le K \le 10$) e segue uma aleatória, mesmo em 1.

Quanto garante ao escolher para maximizar o pior caso?

Exemplo: 3 piscinas, números entre colchetes, 4 escorregas e $K$ igual a 1; diversão fora dos colchetes:

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

Vai sempre de 1 a 3. Livre, escolheria 1 a 2, depois diversão 5 a 3: $5+5=10$. Perder o controlo em 1 pode dar diretamente 3 e 9; em 2 só $5+3 = 8$.

Escolhe $1\to3$ para 9. Se perder o controlo em 1 e seguir $1\to2$, não o perderá em 2 e terá 10. Assim garante pelo menos 9.

Entrada

• Linha $1$: inteiros $V$, $E$, $K$ separados por espaços.
• Linhas $2..E + 1$: a linha $i+1$ contém inteiros $P_{i}$, $Q_{i}$, $F_{i}$ separados por espaços.

Saída

• Linha $1$: um inteiro, a diversão mínima garantida por Bessie.

Exemplos

Entrada 1

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

Saída 1

9

Autor do problema: John Pardon, 2010