Shortest Path in an Undirected Graph

You are given an undirected, connected graph with \(N\) vertices and \(M\) edges. Each edge has a positive integer weight.

Your task is to find the shortest path from vertex 1 to vertex \(N\). If there are multiple shortest paths, you may output any one of them. The output should be the sequence of vertices that forms the shortest path.

inputFormat

The input is read from standard input (stdin). The first line contains two integers \(N\) and \(M\) representing the number of vertices and the number of edges, respectively. Each of the following \(M\) lines contains three integers \(u\), \(v\) and \(w\), indicating there is an edge between vertices \(u\) and \(v\) with weight \(w\).

outputFormat

Output to standard output (stdout) a single line with a sequence of vertices (separated by a space) representing the shortest path from vertex 1 to vertex \(N\). If there is no path, output nothing.

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

1 3 5