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.