A7848. Dijkstra?

You are given a weighted undirected graph. The vertices are enumerated from 1 to $n$ . Your task is to find the shortest path between the vertex $1$ and the vertex $n$ .

The first line contains two integers $n$ and $m$ ( $2<=n<=10^{5},0<=m<=10^{5}$ ), where $n$ is the number of vertices and $m$ is the number of edges. Following $m$ lines contain one edge each in form $a_{i}$ , $b_{i}$ and $w_{i}$ ( $1<=a_{i},b_{i}<=n,1<=w_{i}<=10^{6}$ ), where $a_{i},b_{i}$ are edge endpoints and $w_{i}$ is the length of the edge.

It is possible that the graph has loops and multiple edges between pair of vertices.

Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.