Farmer John sieht jeden Tag gewissenhaft nach den Kühen. Er durchquert einige der $M$ $(1 \le M \le 50,000)$ Wege, die mit $1,\ldots,M$ nummeriert sind, von Weide $1$ bis zur Weide $N$ (für die Wegekarten der Testdaten ist diese Reise immer möglich). Die $N$ $(1 \le N \le 10,000)$ Weiden auf Farmer Johns Farm mit den Nummern $1,\ldots,N$ sind derzeit durch in beide Richtungen begehbare Erdwege verbunden. Jeder Weg $i$ verbindet die Weiden $P1_{i}$ und $P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$ und benötigt $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ Zeiteinheiten zum Durchqueren.

Er möchte einige Wege seiner Farm erneuern, um auf seiner langen Reise Zeit zu sparen. Dazu wählt er $K$ $(1 \le K \le 20)$ Wege aus und verwandelt sie in Schnellstraßen, wodurch ihre Durchquerungszeit effektiv auf $0$ sinkt. Hilf FJ zu entscheiden, welche Wege er erneuern soll, um die Reisezeit von Weide $1$ zu $N$ zu minimieren.

Eingabe

• Zeile 1: drei durch Leerzeichen getrennte ganze Zahlen: $N$, $M$ und $K$.

• Zeilen $2,\ldots,M+1$: Zeile $i+1$ beschreibt Weg $i$ durch drei mit Leerzeichen getrennte ganze Zahlen: $P1_{i}$, $P2_{i}$ und $T_{i}$.

Ausgabe

• Zeile 1: die Länge des kürzesten Weges nach der Erneuerung von höchstens $K$ Kanten.

Beispiele

Eingabe 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

Ausgabe 1

1

Hinweis

$K$ ist $1$; erneuere Weg $3->4$, sodass er $0$ statt $100$ Zeiteinheiten benötigt. Der neue kürzeste Weg ist $1->3->4$, und seine Gesamtdauer beträgt nun $1$.

Aufgabenautor: Percy Liang, 2008