Dijkstra?

给定一张无向有权图，请输出任意一条从 $1$ 到 $n$ 的最短路径。 #### 输入格式 第一行两个整数 $n, m$（$2 \le n \le 10 ^ 5, 0 \le m \le 10 ^ 5$），表示图的点数和边数。 接下来 $m$ 行每行三个整数 $u, v, w$，表示图中有一条从 $u$ 到 $v$ 的边权为 $w$ 的无向边。 #### 输出格式 一个可行的路径，如果不存在这种路径输出 `-1`。

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.

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

1 4 3 5 

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

1 4 3 5