You'll be Working on the Railroad

Time limit1sMemory limit128 MB

Summary

Choose a simple path from town 0 to town 1 in a weighted graph so that the county pays for all sections except the two most expensive ones, then print the path and the county's cost.

Level: Medium7 of 10
Topics: Graph, Shortest path, Brute force
Solved: No attempts yet

Problem

Your county has just won a state grant to install a rail system between its two largest towns, Acmar and Ibmar. The rail system is built in sections; each section connects two different towns, the first section starts at Acmar, and the last section ends at Ibmar.

The grant works as follows: the state pays for the two most expensive sections of the rail system, and the county pays for all the rest.

If the rail system has only two sections, the state pays for just the more expensive of the two.
If the rail system has only one section, the state pays nothing.

The state only considers simple paths: paths that visit any town at most once.

Given cost estimates for connecting various pairs of towns, decide how to build the rail system so that the county pays as little as possible.

Input

The input contains multiple test cases. Each case starts with a line containing a single positive integer $n \le 50$ , the number of section cost estimates. (Not every pair of towns necessarily has an estimate.) The next $n$ lines each contain one estimate as three integers s e c, meaning the estimated cost to build a section between towns $s$ and $e$ is $c$ .

Acmar is always town $0$ and Ibmar is always town $1$ ; the remaining towns are numbered with consecutive integers. Costs are symmetric (the cost between $s$ and $e$ equals the cost between $e$ and $s$ ) and are always positive and at most $1000$ . It is always possible to travel from Acmar to Ibmar by rail using these sections. A line with $n = 0$ signals the end of the input.

Output

For each test case, output a single line of the form

c1 c2 ... cm cost

where $c_1, c_2, \ldots, c_m$ are the towns along the cheapest path, in order, and cost is the amount the county pays. Here $c_1$ is always $0$ (Acmar), $c_m$ is always $1$ (Ibmar), and consecutive towns $c_i$ and $c_{i+1}$ are connected by a section on the path.

If several paths give the same cost to the county, output the one with the fewest sections; if there is still a tie, output the path that comes first lexicographically.

Examples4

Example 1

Input

Expected output

0 3 4 1 3

Example 2
Input
```
1
0 1 42
0
```
Expected output
```
0 1 42
```
Example 3
Input
```
2
0 2 5
2 1 8
0
```
Expected output
```
0 2 1 5
```
Example 4
Input
```
3
0 1 100
0 2 3
2 1 4
0
```
Expected output
```
0 2 1 3
```