Journey through Colors

In the land of Oz, roads are paved with colored stones. Each road connects exactly two cities, can be traveled in both directions, and is colored with stones of a single color.

Dorothy is visiting Oz for the first time and wants to take a tour of the country, meeting the following conditions:

• The tour must start and end in the same city.
• The tour must pass through each road in the country exactly once and cannot use two consecutive roads (i.e., one immediately after the other) that have the same color.
• The first and last roads of the tour must have different colors.

Figure (a) below illustrates an example with five cities and six roads. Figure (b) shows a possible tour that starts and ends in city $2$ and satisfies the road color restrictions. In figure (b), the tour starts in city $2$ and goes, in sequence, through roads $1$ (red), $3$ (green), $4$ (blue), $2$ (red), $6$ (blue) and, finally, $5$ (green).

Help Dorothy find such a tour or, if it is not possible, indicate that it does not exist.

The first line of the input contains three integers, $N$, $M$, and $K$, representing the number of cities ($2 ≤ N ≤ 1000$), the number of roads ($1 ≤ M ≤ 1000$), and the number of colors ($1 ≤ K ≤ 1000$), respectively. Cities are identified by integers from $1$ to $N$, roads are identified by integers from $1$ to $M$, and colors are identified by integers from $1$ to $K$. Each of the following $M$ lines describes a road and contains three integers $I$, $J$, and $C$, where $I$ and $J$ represent cities ($1 ≤ I, J ≤ N$, and $I \ne J$), and $C$ indicates the color of road $1 ≤ C ≤ K$. The roads are given in the order of their identification, that is, the first road in the input is number $1$, the second road is number $2$, and so on.

If there is no tour that satisfies the constraints, print a single integer -1. Otherwise, your program should output two lines describing a valid tour. The first line should contain the identifier of the starting city of the tour. The second line should contain $M$ distinct integers, each identifying a road, in tour order. If there is more than one possible tour, print any one of them.