Two Shortest Paths#4587
Vasya and Petya had a big argument yesterday, and today they want to avoid each other on their way to school. The issue is that they live in the same building, leave for school at the same time, and walk at the same speed along the shortest path. Neither wants to change their routine, so they need to find two different shortest paths to avoid walking together. They don't mind briefly meeting at the nodes of the road network.
They need your help. The nodes are numbered from to , with their home at node and the school at node . There is at most one road between any pair of nodes.
The first line contains two integers, and (2 \le N \le 400), where is the number of roads identified by Petya and Vasya. Each of the next lines contains three integers: , , and (1 \le X, Y \le N, 1 \le L \le 10000), where and are the nodes connected by a road, and is the length of the road.
On the first line, print the node numbers of the first shortest path. On the second line, print the second shortest path. If no solution exists, print "No solution" (without quotes).
Example 1