Farmer John quiere instalar una línea telefónica en su granja. Por desgracia, la compañía telefónica no coopera, así que debe pagar algunos de los cables necesarios para conectar la granja al sistema telefónico.

Hay $N$ postes telefónicos solitarios, $(1 \le N \le 1,000)$, repartidos por su propiedad y convenientemente numerados $1..N$; no hay cables que los conecten. Un total de $P$ parejas de postes, $(1 \le P \le 10,000)$, pueden unirse con un cable; las demás están demasiado alejadas.

El cable $i$ puede conectar los postes distintos $A_i$ y $B_i$, con longitud $L_i$ unidades si se utiliza, $(1 \le L_i \le 1,000,000)$. Los datos de entrada nunca mencionan una pareja {$A_i,B_i$} más de una vez. El poste $1$ ya está conectado al sistema telefónico, y el poste $N$ está en la granja. Los postes $1$ y $N$ deben conectarse mediante un camino de cables; los demás postes pueden usarse o no.

Resulta que la compañía está dispuesta a proporcionar gratuitamente $K$ cables a Farmer John, $(0 \le K < N)$. Por el resto deberá pagar un precio igual a la longitud del cable más largo que aún necesite (cada pareja de postes se une con un cable separado), o $0$ si no necesita cables adicionales.

Determina la cantidad mínima que Farmer John debe pagar.

Entrada

Lee los datos de la entrada estándar.

• Línea 1: tres enteros separados por espacios: $N$, $P$ y $K$.

• Líneas $2..P+1$: la línea $i+1$ contiene tres enteros separados por espacios: $A_i$, $B_i$ y $L_i$.

Salida

Escribe la respuesta en la salida estándar.

• Línea 1: un entero, la cantidad mínima que Farmer John puede pagar. Si es imposible conectar la granja a la compañía telefónica, imprime $-1$.

Ejemplos

Entrada 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

Salida 1

4

Nota

Hay 5 postes. El poste $1$ no puede conectarse directamente a los postes $4$ o $5$. El poste $5$ no puede conectarse directamente a los postes $1$ o $3$. Todas las demás parejas pueden conectarse. La compañía proporcionará un cable gratuito.

Si el poste $1$ se conecta al $3$, el $3$ al $2$ y el $2$ al $5$, Farmer John necesita cables de longitudes $4$, $3$ y $9$. La compañía proporcionará el de longitud $9$, por lo que el cable más largo que queda por cubrir mide $4$.

Autor del problema: Paul Christiano, 2007