Encuentra la ruta más corta 2

Se te proporciona un mapa que consta de n ciudades y m carreteras bidireccionales que conectan estas ciudades. Cada carretera tiene una longitud entera no negativa, representada por . Tu tarea es averiguar la distancia del camino más corto entre la ciudad 1 y la ciudad n.

Entrada

La primera línea contiene dos enteros separados por espacio, n y m (), que representan la cantidad de ciudades y la cantidad de carreteras, respectivamente.

Las siguientes m líneas contienen cada una tres números enteros separados por espacio , y , los cuales describen una carretera entre las ciudades y con longitud ().

Salida

Se debe imprimir un único número entero que represente la longitud del camino más corto desde la ciudad 1 hasta la ciudad n.

Ejemplos

Input

Output

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

6

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue