Excursion

Memory limit: 64 MB

Byteasar is planning an excursion along Byteland. Some pairs of cities in Byteland are connected by bidirectional bus transportation. Byteasar would like his excursion to start and end in the same city and be the cheapest non-empty path that does not use the same bus connection more than once (after taking the route from to he doesn't want to use any of the connections: , any more). Write a program that finds the cheapest closed path along Byteland without any duplicate bus connections or determines that it is not possible to find any such path.

Input

The first line of the input contains two integers and (, ) separated with a single space that represent the number of cities in Byteland and the number of bidirectional bus connections between these cities. Each of the following lines contains three integers , and (, , ): the starting city, the ending city and the cost of the -th connection. Each pair of cities is connected by at most one such connection.

Output

The first line of the output should contain the number of cities visited on the cheapest path (the starting city is counted twice). The next line should contain space-separated integers: the numbers of cities visited on the path.

If there is more than one optimal solution, output any one of them. If there are no solutions, the first and only line of the output should contain a single word BRAK (Polish for none).

Example

For the input data:

5 6
1 4 1
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

the correct result is:

5
1 2 5 3 1

Task author: Krzysztof Duleba.