Description

From CERC 1995

John has many friends living on different streets. He wants to visit each friend while minimizing the total distance traveled. Due to narrow roads, John cannot turn around on a street once he starts traveling on it. John wishes to start from his home, visit all his friends, and return home with the shortest possible total distance. He realizes that the shortest path would involve traversing each street exactly once and returning to the starting point. Write a program to help John find such a path. Each given street connects two intersections. Streets are numbered from $1$ to $n$, and intersections are numbered from $1$ to $m$.

Input Format

Multiple test cases.
Each test case consists of several lines, each containing three integers: $x, y, z$. $z$ is the street number, and $x$ and $y$ are the numbers of the two intersections connected by this street. Self-loops are possible.
For each test case, John lives at the intersection with the smaller number among the two connected by the first street. All streets are interconnected. 0 0 marks the end of a test case.
Another 0 0 marks the end of input.

Output Format

If a circuit that traverses each street exactly once exists, output the found path with integers separated by a single space and no trailing space at the end of the line. If no such path exists, output Round trip does not exist..

Sample 1

1 2 1
2 3 2
3 1 6
1 2 5
2 3 3
3 1 4
0 0
1 2 1
2 3 2
1 3 3
2 4 4
0 0
0 0

1 2 3 5 4 6
Round trip does not exist.

Constraints and Hints

There are at most $1995$ streets and $44$ intersections.