Wędrówki górskie

Limit pamięci: 32 MB

Bajtłomiej jest miłośnikiem wycieczek górskich. Tegoroczne wakacje spędza w Bajtydzie Niskim, pięknych górach na południu Bajtocji. Każdego ranka Bajtłomiej wyrusza na wycieczkę z jednego ze schronisk i wędruje taką trasą by wieczorem wrócić do tego samego schroniska (każdego dnia może wybrać inne schronisko początkowe). Bajtłomiej jest jednak dosyć wybrednym bajternikiem - w ciągu dnia nigdy nie przechodzi koło tego samego schroniska dwa razy. Ponadto, codzienne po zakończonej wyprawie wybiera najnudniejszy szlak spośród tych które danego dnia przebył (jeśli kilka szlaków było równie nudnych, wybiera dowolny z nich) i wykreśla go ze swojej mapy. Od tego momentu już nigdy nie przejdzie po tym szlaku. Gdy już wykreśli tyle szlaków, że nie będzie mógł zaplanować żadnej wędrówki spełniającej jego wymagania, pakuje swój plecak i wraca do domu.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis szlaków w Bajtydzie Niskim,
• wyznaczy szlaki, które Bajtłomiej wykreśli ze swojej mapy,
• zapisuje odpowiedź na standardowe wyjście.

Wejście

W pierwszej linii standardowego wejścia znajdują się dwie liczby całkowite i . Oznaczają one odpowiednio liczbę schronisk oraz liczbę szlaków w Bajtydzie Niskim. Kolejne linii zawiera opisy szlaków. -ta spośród nich zawiera opis szlaku o numerze - trzy liczby całkowite , i pooddzielane spacjami . Oznaczają one, że schroniska i łączy szlak, którego współczynnik ciekawości wynosi (im niższy współczynnik ciekawości tym nudniejszy jest dany szlak). Pomiędzy parą schronisk istnieje co najwyżej jeden szlak.

Wyjście

W pierwszej linii standardowego wyjścia należy wypisać jedną liczbę całkowitą - ilość wędrówek, na które udał się Bajtłomiej. Druga linia powinna zawierać liczb pooddzielanych spacjami - numery kolejnych szlaków wykreślanych przez Bajtłomieja z jego mapy. Jeżeli istnieje wiele różnych rozwiązań, to wystarczy wypisać jedno z nich.

Przykład

Dla danych wejściowych:

5 5
1 2 5
2 3 4
3 4 5
4 1 2
3 5 3

poprawną odpowiedzią jest:

1
4

Autor zadania: Jakub Łącki.