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.
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.