Inspiriert vom neuen Wasserpark in Machu Picchu in Peru baut Farmer John einen für die Kühe. Die Hauptattraktion ist eine riesige Wasserrutsche besonderer Bauart.

Sie besteht aus $E$ ($1 \le E \le 150,000$) kleinen Rutschen zwischen $V$ ($2 \le V \le 50,000$) Becken $1..V$. Jede darf nur vorwärts durchfahren werden. Die Kühe starten in 1 und enden in $V$. Außer 1 hat jedes Becken mindestens eine eingehende Rutsche, außer $V$ mindestens eine andere ausgehende.

Von jedem Becken erreicht man das Ende $V$. Man kann keines verlassen und nach mehreren Rutschen wieder erreichen.

Rutsche $i$ führt von $P_{i}$ zu $Q_{i}$ ($1 \le P_{i} \le V; 1 \le Q_{i} \le V; P_{i} \ne Q_{i}$) mit Spaßwert $F_{i}$ ($0 \le F_{i} \le 2,000,000,000$). Bessies Gesamtspaß ist die Summe der Werte aller durchfahrenen Rutschen.

Nach langem Warten möchte sie möglichst viel Spaß. Normalerweise wählt sie Ausgänge sorgfältig, verliert aber höchstens $K$-mal ($1 \le K \le 10$) die Kontrolle und nimmt einen zufälligen Ausgang, auch in 1 möglich.

Wie viel garantiert sie, wenn sie den Spaß im schlechtesten Fall maximiert?

Beispiel: 3 Becken, Nummern in Klammern, 4 Rutschen und $K$ gleich 1; Spaß außerhalb der Klammern:

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

Stets von 1 nach 3. Frei würde sie 1 nach 2 und dann die Rutsche mit Spaß 5 nach 3 wählen: $5+5=10$. Kontrollverlust in 1 kann direkt 3 mit 9 ergeben, in 2 nur $5+3 = 8$.

Sie wählt $1\to3$ für 9. Verliert sie in 1 die Kontrolle und nimmt $1\to2$, verliert sie sie in 2 nicht mehr und erhält 10. Mindestens 9 sind garantiert.

Eingabe

• Zeile $1$: durch Leerzeichen getrennte ganze Zahlen $V$, $E$, $K$.
• Zeilen $2..E + 1$: Zeile $i+1$ enthält durch Leerzeichen getrennte ganze Zahlen $P_{i}$, $Q_{i}$, $F_{i}$.

Ausgabe

• Zeile $1$: eine ganze Zahl, der garantierte minimale Spaß.

Beispiele

Eingabe 1

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

Ausgabe 1

9

Autor der Aufgabe: John Pardon, 2010