Input will contain multiple test cases. Each case will start with a line containing a single positive integer n <= 50, indicating the number of railway section estimates. (There may not be estimates for tracks between all pairs of towns.) Following this will be n lines each containing one estimate. Each estimate will consist of three integers s e c, where s and e are the starting and ending towns and c is the cost estimate between them. (Acmar will always be town 0 and Ibmar will always be town 1. The remaining towns will be numbered using consecutive numbers.) The costs will be symmetric, i.e., the cost to build a railway section from town s to town e is the same as the cost to go from town e to town s, and costs will always be positive and no greater than 1000. It will always be possible to somehow travel from Acmar to Ibmar by rail using these sections. A value of n = 0 will signal the end of input.
For each test case, output a single line of the form
c1 c2 ... cm cost
where each ci is a city on the cheapest path and cost is the cost to the county (note c1 will always be 0 and cm will always be 1 and ci and ci+1 are connected on the path). In case of a tie, print the path with the shortest number of sections; if there is still a tie, pick the path that comes first lexicographically.
7 0 2 10 0 3 6 2 4 5 3 4 3 3 5 4 4 1 7 5 1 8 0
0 3 4 1 3
NOTE: problem H from 2008 East Central Regional Contest.