Inspiré du nouveau parc aquatique à Machu Picchu au Pérou, Farmer John décide d’en construire un pour les vaches. L’attraction principale sera un immense toboggan de conception particulière.

Il comprend $E$ ($1 \le E \le 150,000$) petits toboggans reliant $V$ ($2 \le V \le 50,000$) bassins $1..V$. Chaque toboggan est à sens unique. Les vaches partent de 1 et glissent jusqu’au dernier bassin $V$. Chaque bassin sauf 1 a au moins un toboggan entrant, chaque bassin sauf $V$ au moins un autre sortant.

De tout bassin, on peut atteindre la fin $V$. On ne peut quitter un bassin puis y revenir après plusieurs toboggans.

Le toboggan $i$ va de $P_{i}$ à $Q_{i}$ ($1 \le P_{i} \le V; 1 \le Q_{i} \le V; P_{i} \ne Q_{i}$), avec un plaisir $F_{i}$ ($0 \le F_{i} \le 2,000,000,000$). Le plaisir total de Bessie est la somme des valeurs parcourues.

Après une longue attente, elle veut le maximum. Elle choisit normalement ses sorties, mais perd le contrôle au plus $K$ fois ($1 \le K \le 10$) et suit une sortie aléatoire, même au bassin 1.

Quel plaisir garantit-elle en choisissant pour maximiser le pire cas ?

Exemple : 3 bassins, numéros entre crochets, 4 toboggans et $K$ égal à 1 ; plaisir hors crochets :

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

Elle va toujours de 1 à 3. Libre, elle choisirait 1 vers 2 puis le toboggan de plaisir 5 vers 3 : $5+5=10$. Perdre le contrôle en 1 peut donner directement 3 et 9, en 2 seulement $5+3 = 8$.

Elle préfère $1\to3$, plaisir 9. Si elle perd le contrôle en 1 et prend $1\to2$, elle ne le perdra plus en 2 et obtiendra 10. Elle garantit donc au moins 9.

Entrée

• Ligne $1$ : entiers $V$, $E$, $K$ séparés par des espaces.
• Lignes $2..E + 1$ : la ligne $i+1$ contient les entiers $P_{i}$, $Q_{i}$, $F_{i}$ séparés par des espaces.

Sortie

• Ligne $1$ : un entier, le plaisir minimal garanti par Bessie.

Exemples

Entrée 1

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

Sortie 1

9

Auteur du problème : John Pardon, 2010