Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

graphs

shortest paths

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Dijkstra?

time limit per test

1 secondmemory limit per test

64 megabytesinput

standard inputoutput

standard outputYou 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*.

Input

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.

Output

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.

Examples

Input

5 6

1 2 2

2 5 5

2 3 4

1 4 1

4 3 3

3 5 1

Output

1 4 3 5

Input

5 6

1 2 2

2 5 5

2 3 4

1 4 1

4 3 3

3 5 1

Output

1 4 3 5

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2024 06:16:26 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|