Enojado porque el lanzamiento de la tercera parte de su película favorita se pospuso hasta junio de 2020, Megazar y Gigazar pensaron en su propio guion para el final de la trilogía: En un mundo donde los vikingos de IslaGrande pueden volar con dragones, hay ~N~ islas. Bytezar, el jefe de la tribu vikinga en la Isla ~1~, conoce rutas de vuelo directo de ida y vuelta entre las islas. Para cada ~j~ entre ~1~ y ~M~, la ruta ~j~ une las islas ~A_j~ y ~B_j~ y tiene una longitud ~D_j~.

En cada isla ~i~, (~1 \le i \le N~) hay dragones de la especie que pueden volar sin detenerse a una distancia máxima de ~Dmaxi~. En otras palabras, los dragones en la isla podrán recorrer cualquier ruta ~j~, (~1 \le j \le M~) para la cual ~Dj \le Dmaxi~, sin importar qué otras vías de vuelo hayan hecho previamente.

Bytezar quiere ir de la isla ~1~ a la isla ~N~ para salvar a Terazar, su dragón. Para llegar allí, inicialmente tomará un dragón de la especie ~1~ (en la isla ~1~). Entonces, si en algún momento Bytezar está en una isla, (~1 \le i \le N~) con un dragón de la especie ~T~, puede:

1. Vuela de la isla ~i~ a otra isla ~x~ con el dragón que tiene, usando una ruta directa ~j~ entre las islas i y x, por supuesto solo si ~Dj \le Dmaxt~.

2. Cambiar el dragón de la especie que tiene con un dragón de la especie en la isla.

Tarea

a) Determine la distancia máxima Dmaxi característica de un dragón a la que Bytezar puede llegar sin cambiar el dragón que tomó originalmente de la isla ~1~.

b) Determine la distancia mínima que debe recorrer Bytezar para llegar de la isla ~1~ a la isla ~N~.

Especificación de la Entrada

El archivo de entrada estándar contiene en la primera línea un número natural P. Para todas las pruebas de entrada, el número P solo puede tener el valor ~1~ o el valor ~2~. En la segunda línea hay dos números naturales N y M que representan el número de islas, y el número de rutas directas entre islas respectivamente. En la tercera línea hay N números naturales, el tercero de ellos representa la distancia máxima ~Dmaxi~ que un dragón puede volar desde la Isla. Las siguientes líneas se describen en las siguientes líneas. Hay tres números naturales A, B y D en cada una de estas líneas, lo que significa que hay una ruta bidireccional de longitud D entre las islas A y B.

Especificación de la Salida

En el archivo de salida estándar se mostrará un único número natural.

Si el valor de ~P~ es ~1~, solo se resuelve el requisito ~a~.

En este caso, el número que se muestra representará la distancia máxima Dmaxi de un dragón ~i~ a la que Bytezar puede llegar sin cambiar el dragón que tomó originalmente de la isla ~1~.

Si el valor de ~P~ es ~2~, solo se resolverá el requisito ~b~.

En este caso, el número que se muestra representará la distancia mínima que Bytezar debe recorrer para llegar de la isla ~1~ a la isla ~N~.

Restricciones y especificaciones

• ~1 \le N \le 800~
• ~1 \le M \le 6000~
• ~1 \le Dmax \le 50 000~, para cualquier ~1 \le y \le N~.
• ~1 \le Aj~, ~Bj \le N~, para cualquier ~1 \le j \le M~.
• ~1 \le Dj \le 50 000~, para cualquier ~1 \le j \le M~.
• Se garantiza que Bytezar puede llegar a la isla ~N~.
• Se garantiza que la respuesta a cualquier requisito es un número natural menor que ~10^9~.
• Para resolver el primer requisito correctamente, se otorga el ~20~ % de la puntuación de la prueba.
• Para la solución correcta del segundo requisito, se otorga el ~80~ % de la puntuación de la prueba.

Ejemplos #1 de Entrada

1
5 6
6 3 13 20 26
1 2 5
1 3 7
1 5 10
2 3 6
3 4 5
3 5 14

Ejemplos #1 de Salida

20

Explicación #1

~P = 1~, por lo que se resolverá el requisito ~a~).

Hay ~N = 5~ islas y ~M = 6~ rutas entre ellas. Bytezar comienza desde la isla ~1~ con un dragón que puede volar una distancia de hasta ~6~. Con este dragón solo puede llegar a las islas ~1~, ~2~, ~3~ y ~4~, ya que para llegar a la isla ~5~ tendría que recorrer una ruta. Longitud mayor que ~6~.

La distancia máxima que un dragón en las islas ~1~, ~2~, ~3~ o ~4~ puede volar es por lo tanto ~20~ (el dragón en la isla ~4~). Se puede ver que el dragón que puede volar una distancia de ~26~ estaba en la isla ~5~ y es inaccesible.

Ejemplos #2 de Entrada

2
5 6
6 3 13 20 26
1 2 5
1 3 7
1 5 10
2 3 6
3 4 5
3 5 14

Ejemplos #2 de Salida

28

Explicación #2

~P = 2~, por lo que se resolverá el requisito ~b~).

Hay ~N = 5~ islas y ~M = 6~ rutas entre ellas. Para cubrir una distancia mínima de ~28~ entre las islas ~1~ y ~N~, Bytezar sigue los siguientes pasos:

Vuela de la isla ~1~ a la isla ~2~ una distancia de ~5~ con el dragón de la especie ~1~. Vuela de la isla ~2~ a la isla ~3~ una distancia de ~6~ con el dragón de la especie ~1~. Cambia el dragón de la especie ~1~ con el dragón en la isla ~3~, que puede volar una distancia máxima de ~13~. Vuela de la isla ~3~ a la isla ~1~ una distancia de ~7~ con el dragón de la especie ~3~. Vuela de la isla ~1~ a la isla ~5~ una distancia de ~10~ con el dragón de la especie ~3~.

En total corre una distancia de ~5 + 6 + 7 + 10 = 28~.