Shortest Path in an Undirected Graph

You are given an undirected weighted graph with n nodes and m edges. Each edge is described by a triplet \( (u, v, w) \) where \( u \) and \( v \) are the vertices connected by the edge and \( w \) is its weight. Your task is to compute one of the shortest paths from a given source node \( a \) to a target node \( b \) using Dijkstra's algorithm.

If there exist multiple shortest paths, output any one of them. The result should be a sequence of node indices starting from \( a \) and ending at \( b \) that corresponds to the shortest path.

Note: If no path exists, output an empty line.

inputFormat

The input is read from stdin and is formatted as follows:

1. The first line contains two integers \( n \) and \( m \): the number of nodes and the number of edges.
2. The second line contains two integers \( a \) and \( b \): the source and target nodes.
3. The next \( m \) lines each contain three integers \( u \), \( v \), \( w \) describing an undirected edge connecting nodes \( u \) and \( v \) with weight \( w \).

outputFormat

Output the nodes along one of the shortest paths from \( a \) to \( b \) separated by spaces, in order, on a single line. If there is no valid path, output an empty line.

## sample

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

1 2 3 5

</p>