Farmer John möchte einen Telefonanschluss auf seinem Hof einrichten. Leider ist die Telefongesellschaft nicht kooperativ, sodass er einige der Kabel bezahlen muss, die seinen Hof mit dem Telefonnetz verbinden sollen.

Auf seinem Grundstück stehen verstreut $N$ einsame Telefonmasten, $(1 \le N \le 1,000)$, die praktischerweise mit $1..N$ nummeriert sind; keine Kabel verbinden sie. Insgesamt $P$ Mastpaare, $(1 \le P \le 10,000)$, können durch ein Kabel verbunden werden; die anderen sind zu weit voneinander entfernt.

Das $i$-te Kabel kann die verschiedenen Masten $A_i$ und $B_i$ verbinden und hat bei Verwendung die Länge $L_i$ Einheiten, $(1 \le L_i \le 1,000,000)$. Die Eingabe nennt kein Paar {$A_i,B_i$} mehr als einmal. Mast $1$ ist bereits mit dem Telefonnetz verbunden, und Mast $N$ steht am Hof. Die Masten $1$ und $N$ müssen durch einen Kabelpfad verbunden werden; die übrigen Masten können benutzt werden oder nicht.

Wie sich herausstellt, stellt die Telefongesellschaft Farmer John $K$ Kabel kostenlos zur Verfügung, $(0 \le K < N)$. Darüber hinaus muss er einen Preis zahlen, der der Länge des längsten noch benötigten Kabels entspricht (jedes Mastpaar wird mit einem eigenen Kabel verbunden), oder $0$, wenn er keine zusätzlichen Kabel benötigt.

Bestimme den kleinsten Betrag, den Farmer John zahlen muss.

Eingabe

Lies die Eingabe von der Standardeingabe.

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

• Zeilen $2..P+1$: Zeile $i+1$ enthält drei durch Leerzeichen getrennte ganze Zahlen: $A_i$, $B_i$ und $L_i$.

Ausgabe

Schreibe die Ausgabe auf die Standardausgabe.

• Zeile 1: eine ganze Zahl, der kleinste Betrag, den Farmer John zahlen kann. Wenn der Hof nicht mit der Telefongesellschaft verbunden werden kann, gib $-1$ aus.

Beispiele

Eingabe 1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

Ausgabe 1

4

Hinweis

Es gibt 5 Masten. Mast $1$ kann nicht direkt mit Mast $4$ oder $5$ verbunden werden. Mast $5$ kann nicht direkt mit Mast $1$ oder $3$ verbunden werden. Alle anderen Paare können verbunden werden. Die Gesellschaft stellt ein Kabel kostenlos bereit.

Wenn Mast $1$ mit Mast $3$, Mast $3$ mit Mast $2$ und Mast $2$ mit Mast $5$ verbunden wird, benötigt Farmer John Kabel der Längen $4$, $3$ und $9$. Die Gesellschaft stellt das Kabel der Länge $9$ bereit, sodass das längste noch benötigte Kabel die Länge $4$ hat.

Autor der Aufgabe: Paul Christiano, 2007