A usted le dan un grafo dirigido con pesos. Los vértices son enumerados de 1 a n. Su tarea es de encontrar el camino más corto entre el vértice 1 y n.

La entrada consiste de de dos enteros n y m ($2\le ,m,n\le 10^5$), donde n es el numero de vértices y m el numero de arcos. Luego siguen m lineas que contienen un arco en la forma $2\le a_i,b_i,w_i\le 10^6$), donde $a_i,b_i$ representa el arco desde el nodo donde comienza y el que finaliza, $w_i$ representa el peso del arco.

Es posible que el grafo tenga ciclos y múltiples arcos entre dos vértices.

Escriba en la salida el camino mas corto, si no hay un camino  escriba $-1$.

 Implementar el algoritmo de Dijskstra