In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.
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.
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).
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.