Zainspirowany nowym parkiem wodnym w Machu Picchu w Peru Farmer John buduje taki dla krów. Główną atrakcją będzie ogromna zjeżdżalnia o nietypowej konstrukcji.

Składa się z $E$ ($1 \le E \le 150,000$) małych zjeżdżalni łączących $V$ ($2 \le V \le 50,000$) basenów $1..V$. Można jechać wyłącznie w odpowiednim kierunku. Krowy zaczynają w 1 i kończą w $V$. Każdy basen poza 1 ma co najmniej jedną zjeżdżalnię wchodzącą; poza $V$ co najmniej inną wychodzącą.

Z każdego basenu można dotrzeć do końca $V$. Nie można opuścić basenu i wrócić po przejechaniu zjeżdżalni.

Zjeżdżalnia $i$ biegnie z $P_{i}$ do $Q_{i}$ ($1 \le P_{i} \le V; 1 \le Q_{i} \le V; P_{i} \ne Q_{i}$), z frajdą $F_{i}$ ($0 \le F_{i} \le 2,000,000,000$). Łączna frajda Bessie to suma wartości przejechanych zjeżdżalni.

Po długim czekaniu chce maksimum frajdy. Zwykle starannie wybiera wyjścia, ale jako krowa traci kontrolę najwyżej $K$ razy ($1 \le K \le 10$) i jedzie losowym wyjściem, nawet w 1.

Ile gwarantuje, wybierając dla maksimum w najgorszym przypadku?

Przykład: 3 baseny, numery w nawiasach, 4 zjeżdżalnie i $K$ równe 1; frajda poza nawiasami:

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

Zawsze od 1 do 3. Sama wybrałaby 1 do 2, potem wyższą frajdę 5 do 3: $5+5=10$. Utrata kontroli w 1 może dać od razu 3 i 9, w 2 tylko $5+3 = 8$.

Wybiera $1\to3$ dla 9. Jeśli w 1 straci kontrolę i pojedzie $1\to2$, w 2 już jej nie straci i dostanie 10. Gwarantuje co najmniej 9.

Wejście

• Wiersz $1$: całkowite $V$, $E$, $K$ oddzielone spacjami.
• Wiersze $2..E + 1$: wiersz $i+1$ zawiera całkowite $P_{i}$, $Q_{i}$, $F_{i}$ oddzielone spacjami.

Wyjście

• Wiersz $1$: jedno całkowite, minimalna frajda gwarantowana przez Bessie.

Przykład

Wejście 1

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

Wyjście 1

9

Autor zadania: John Pardon, 2010