An undirected weighted graph is given. Find the weight of the minimal path between two vertices.
The first line contains positive integers , , and — the number of vertices and edges in the graph and the numbers of vertices between which the length of the minimum path should be found.
Each of the next lines contains three positive integers , and — the ends of the -th edge and its weight .
Print in the first line the minimum weight of the path between vertices and . In the second line print the vertices on the shortest path from to in the bypass order, space separated. If the route from to does not exist, print .