Segunda Ruta Más Corta

Se te proporcionan n ciudades y m caminos bidireccionales que las conectan. Cada camino tiene una longitud asociada . Emil, un viajero intrépido, quiere ir desde la ciudad 1 hasta la ciudad n utilizando estos caminos. Sin embargo, tiene un giro particular en su plan: elegirá la ruta más corta dentro de todas las que sean estrictamente más largas que la ruta más corta general.

En otras palabras, tu tarea es ayudar a Emil a determinar la longitud de la segunda ruta más corta desde la ciudad 1 hasta la ciudad n.

Entrada

La primera línea de la entrada contiene dos números enteros n y m, que indican la cantidad de ciudades y la cantidad de caminos, respectivamente.
Las siguientes m líneas contienen tres enteros , y , señalando que existe un camino bidireccional entre la ciudad y la ciudad con longitud .

Salida

Imprime un único entero que represente la longitud de la segunda ruta más corta desde la ciudad 1 hasta la ciudad n.

Ejemplos