There is a lot of caves in Byteland. This is the map of one of them:

All caves in Byteland have the following properties:

• All the chambers and passages are on the same level.
• No two passages cross each other.
• Some of the chambers are situated on the outer circle. They are called outer chambers.
• All the other chambers lie inside the outer circle and are called inner chambers.
• There is an entrance to the cave leading to one of the outer chambers.
• There are exactly three passages leading from every chamber to three different other chambers. If a chamber is an outer chamber then two of the passages lead to two neighbouring outer chambers on the circle and exactly one leads to an inner chamber.
• Passages connecting outer chambers are called outer passages and the remaining ones are called inner passages.
• It is possible to walk from one chamber to another using only inner passages but there is only one way to do that if we allow to walk through every inner passage at most once.
• Not all passages are equally hard to go through. They are divided into two groups: easy and hard.

It has been decided to open all the caves to the public. To assure a "smooth" and safe flow through a cave, visitors should follow a route marked in advance and visit every chamber of this cave exactly once. An exception from this rule is the entrance chamber where every tour begins and ends, you are allowed to visit this chamber exactly twice. The tour route should be fit for an average visitor and contain as few hard passages to walk through as possible.

Example

Task

• reads the description of a cave from the text file CAV.IN;
• finds a route through the cave that begins and ends in the entrance chamber, lets the visitors see all the other chambers only once and contains as few hard passages as possible;
• writes the result to the text file CAV.OUT

Input

The next 3n / 2 lines contain descriptions of the passages. Each description consists of three integers a, b, c separated by single spaces. The integers a and b are numbers of chambers at the ends of a passage. The integer c equals 0 or 1, where 0 means that the passage is easy to walk through and 1 that it is hard.

Output

Sample Input

8 5
1 3 0
3 2 0
7 3 1
7 2 0
8 7 0
1 8 0
6 8 0
6 4 0
6 5 1
5 4 0
2 4 0
5 1 0

Sample Output

1 5 4 6 8 7 2 3