Los azucareros del centro pasean por el Jardín del Mar y se encuentran en apuros: han comprado un perro de raza y debe protegerlo de animales salvajes. La situación se complica aún más, ya que el parque ha implementado la circulación en un solo sentido en los senderos. Formalmente, el Jardín del Mar puede representarse como un grafo dirigido y acíclico, con ~N~ vértices, numerados del ~1~ al ~N~, y ~M~ aristas. Cada vértice representa uno de los ~N~ jardines, con Pedro el azucarero en el jardín número ~1~. Las aristas del grafo representan los senderos del parque que conectan los jardines y tienen coeficientes de peligrosidad que indican el riesgo de que un animal salvaje le robe el perro al azucarero. A pesar del peligro, Pedro el azucarero quiere dar un paseo completo, así que busca un camino en el grafo que contenga exactamente ~K~ aristas, para poder caminar sin cansarse demasiado. Como aún quiere pasear, elige los senderos de forma que el mayor peligro en cualquier sendero sea mínimo. También es posible que no exista ningún camino con exactamente ~K~ aristas.

Escribe un programa que determine si existe un camino de longitud ~K~ que comience en el vértice ~1~ y, de ser así, que encuentre el riesgo mínimo de dicho camino, donde el riesgo del camino es igual al riesgo máximo de una arista del mismo.

Entrada

• La primera línea de la entrada contiene los enteros positivos ~N, M~ y ~K~, que representan, respectivamente, el número de jardines, el número de senderos y la longitud deseada del recorrido.
• Las ~M~ líneas restantes de la entrada describen los senderos. La i-ésima línea contiene tres enteros positivos, ~v_i, u_i~ y ~d_i~, que caracterizan un sendero que va del jardín ~v_i~ al jardín ~u_i~ con un riesgo ~d_i~.

Salida

Imprime en la salida un número igual al riesgo mínimo de un camino de longitud exactamente ~K~ senderos comenzando en el jardín ~1~. Si no existe tal camino, imprime ~-1~.

Restricciones

• ~1 \leq N, K \leq 200 000~
• ~1 \leq M \leq 500 000~
• ~1 \leq v_i, u_i \leq N~
• ~1 \leq d_i \leq 10^9~

Subtareas

Subtarea	Puntos	N	K	Otras restricciones
0	0	–	–	Pruebas de ejemplo
1	10	~\leq 10~	~\leq 45~	–
2	10	~\leq 20~	~\leq 70~	–
3	20	~\leq 1000~	~\leq 2500~	–
4	10	~\leq 6000~	~\leq 15000~	–
5	15	~\leq 2\cdot10^5~	~\leq 5\cdot10^5~	~d_i=1~
6	35	~\leq 2\cdot10^5~	~\leq 5\cdot10^5~	–

Ejemplo #1 de Entrada

13 18 4
1 2 4
1 3 1
2 4 6
2 5 4
2 6 2
3 6 3
3 10 4
4 7 6
5 8 5
6 8 2
10 11 6
7 8 5
11 12 7
12 8 6
7 9 5
9 13 6
13 8 1
5 6 3

Ejemplo #1 de Salida

4

En la imagen se muestra uno de los recorridos óptimos.

Cada jardín se representa con un círculo y cada sendero con una flecha.

Ejemplo #2 de Entrada

4 4 3
1 2 5
1 3 6
3 2 4
1 4 1

Ejemplo #2 de Salida

-1

No existe ningún recorrido de esta longitud.