Two Shortest Paths
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 1 to N, with their home at node 1 and the school at node N. There is at most one road between any pair of nodes.
Input
The first line contains two integers, N and M (2 ≤ N ≤ 400), where M is the number of roads identified by Petya and Vasya. Each of the next M lines contains three integers: X, Y, and L (1 ≤ X, Y ≤ N, 1 ≤ L ≤ 10000), where X and Y are the nodes connected by a road, and L is the length of the road.
Output
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).