Tu tarea es encontrar la ruta de vuelo más económica entre Syrjälä y Metsälä. Dispones de un cupón de descuento con el que puedes reducir a la mitad el precio de cualquier vuelo durante el trayecto. Sin embargo, solo puedes usar el cupón una vez.

Cuando usas el cupón de descuento para un vuelo cuyo precio es ~x~, su precio se convierte en ~\lfloor x/2 \rfloor~ (se redondea hacia abajo al entero más cercano).

Entrada

La primera línea de entrada contiene dos enteros, ~n~ y ~m~: el número de ciudades y conexiones de vuelo. Las ciudades están numeradas del ~1~ al ~n~. La ciudad ~1~ es Syrjälä y la ciudad ~n~ es Metsälä.

A continuación, hay ~m~ líneas que describen los vuelos. Cada línea contiene tres enteros, ~a, b~ y ~c~: un vuelo comienza en la ciudad ~a~, termina en la ciudad ~b~ y su precio es ~c~. Cada vuelo es unidireccional. Se asume que siempre es posible ir de Syrjälä a Metsälä.

Salida

Imprime un número entero: el precio de la ruta más económica de Syrjälä a Metsälä.

Restricciones

• ~2 \leq n \leq 10^5~
• ~1 \leq m \leq 2 \cdot 10^5~
• ~1 \leq a,b \leq n~
• ~1 \leq c \leq 10^9~

Ejemplo de Entrada

3 4
1 2 3
2 3 1
1 3 7
2 1 5

Ejemplo de Salida

2