← 返回题目

题库练习 Dijkstra?

← 上一题下一题 →

A7848 | $Dijkstra?$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

输出 #1

1 4 3 5

输入 #2

输出 #2

1 4 3 5

C++ 编辑器

输入

输出