Wycieczka

Limit pamięci: 64 MB

Jaś zamierza wyruszyć na wycieczkę po Bajtocji. Między miastami Bajtocji istnieją dwukierunkowe połączenia autobusowe. Jaś zastanawia się, jaka trasa tam i z powrotem kosztowałaby najmniej, jeśli dane połączenie może być użyte tylko raz (czyli po przejechaniu autobusem z A do B nie możemy nim wrócić z B do A). Pomóż Jasiowi rozwiązać jego problem.

Zadanie

Napisz program, który:

• wczyta opis połączeń autobusowych w Bajtocji
• wypisze na standardowe wyjście dowolną najtańszą niepustą zamkniętą trasę po Bajtocji lub BRAK w przypadku braku rozwiązania.

Wejście

W pierwszym wierszu wejścia podane są dwie liczby naturalne, (liczba miast) i (liczba dwukierunkowych połączeń), , . W każdym z następnych wierszy znajdują się trzy liczby , , (, ): początek, koniec i koszt -tego połączenia.

Między daną parą miast istnieje co najwyżej jedno połączenie.

Wyjście

W pierwszym wierszu wyjścia ma się znajdować liczba odwieczonych miast (początek i koniec liczymy osobno) na najtańszej zamkniętej niepustej trasie. W następnym wierszu ma się znajować liczb naturalnych: numery kolejno odwiedzanych miast.

W przypadku istnienia wielu rozwiązań można wypisać dowolne z nich, w przypadku braku rozwiązań w jedynym wierszu wyjścia należy wpisać BRAK.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

5
1 2 5 3 1

Autor zadania: Krzysztof Dulęba.