题目描述

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.

题面翻译

题目大意

给出一张图，请输出其中任意一条可行的从点 $1$ 到点 $n$ 的最短路径。

输入输出格式

输入格式

第一行：两个整数n，m，分别表示点数和边数

接下来m行：每行三个整数u，v，w，表示u和v之间连一条边权为w的双向边。

输出格式

一行：一个可行的路径，如果不存在这种路径输出-1

$2<=n<=10^5，0<=m<=10^5$

样例 #1

样例输入 #1

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

样例输出 #1

1 4 3 5

样例 #2

样例输入 #2

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

样例输出 #2

1 4 3 5