Description

John has many friends living on different streets and wants to visit each friend while traveling as little as possible. Because the streets are narrow, John cannot go back along the same street. He wants to start from his home, visit all his friends, and return home, with the minimum total distance. John realizes that if he can traverse each street exactly once and return to the starting point, that should be the shortest route. Write a program to help John find such a route. Each street connects two intersections. The streets are numbered from $1$ to $n$, and the intersections are numbered from $1$ to $m$.

Input Format

Multiple testcases.

Each testcase consists of several lines, each line containing three integers: $x, y, z$. Here, $z$ is the index of the street, and $x$ and $y$ are the indices of the two intersections that the street connects. Self-loops may appear.

For each testcase, John lives at the intersection with the smaller index among the two intersections listed on the first line. The graph is connected.

A line containing two integers 0 0 ends the current testcase. Two consecutive lines 0 0 indicate the end of input.

Output Format

If there exists a circuit that traverses every street exactly once, output the route found as a sequence of street indices in the traversal order, with a single space between adjacent integers and no trailing space at the end of the line. Otherwise, output Round trip does not exist..

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.

Hint

At most $1995$ streets and at most $44$ intersections.

Translated by ChatGPT 5