CEOI'97 - Nowy Sącz

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

Consider the cave showed in the figure. The entrance chamber is 1. The dashed passages are hard to walk through. Route 1, 5, 4, 6, 8, 7, 2, 3 contains no hard passages at all. The final chamber, number 1, is implied and not listed.

Task

Write a program that:

• 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

There are two integers n, k (separated by a single space) in the first line of the text file CAV.IN The integer n, 3 < n <= 500, is the number of all chambers in a cave and k is the number of all its outer chambers, k >= 3. The chambers are numbered from 1 to n. Chamber 1 is the entrance chamber. Chambers 1, 2, ..., k are outer chambers. They do not have to appear on the outer circle in this order.

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

Your program should write a sequence of n integers separated by single spaces to the first line of the text file CAV.OUT; the sequence has to begin with 1 (the entrance chamber). The following n - 1 integers should be consecutive chambers on the computed route.

Example

For the text file CAV.IN:

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

1 5 4 6 8 7 2 3

Print friendly version