Dijkstra模板题

题目描述

给定一张无向有权图，请输出任意一条从 \(1\) 到 \(n\) 的最短路径。

输入格式

第一行两个整数 \(n, m\)（\(2 \le n \le 10 ^ 5, 0 \le m \le 10 ^ 5\)），表示图的点数和边数。

接下来 \(m\) 行每行三个整数 \(u, v, w\)（\(1\leq u,v\leq n,1\leq w\leq10^6\)），表示图中有一条从 \(u\) 到 \(v\) 的边权为 \(w\) 的无向边。

输出格式

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

输入输出样例 #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