Shortest Path in an Undirected Graph

You are given an undirected graph consisting of n cities and m roads. Each road connects two distinct cities with an associated travel time.

Your task is to compute the shortest path from a starting city s to a destination city t by using Dijkstra's algorithm. In mathematical terms, you are asked to minimize the total travel time:

\(\text{minimize} \; \sum_{(u,v) \in P} t_{uv}\)

If there are multiple shortest paths, any one of them is acceptable. If there is no valid path from s to t, output NONE.

inputFormat

The input is given via standard input (stdin) and has the following format:

The first line contains a single integer n, the number of cities. The second line contains two integers s and t, representing the starting and destination cities respectively. The third line contains an integer m, the number of roads. Each of the next m lines contains three integers u, v, and w, indicating that there is a bidirectional road between city u and city v with a travel time of w.

Constraints: It is guaranteed that 1 ≤ n, m ≤ 10^5 and 1 ≤ u, v, s, t ≤ n.

outputFormat

Print the cities along the shortest path from s to t in order, separated by a single space. If no path exists, print "NONE".## sample

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

1 3 4 5