Bug [A]

Limit pamięci: 64 MB

Twój kalendarz elektroniczny ma błąd, czyli coś, co informatycy nazywają bugiem. Otóż nie można do niego wpisywać liczb całkowitych parzystych.

Planujesz pojechać służbowo z Bajtogrodu do Bitowic. Oczywiście, najlepiej by było przybyć do celu najkrótszą trasą. Po powrocie długość trasy będziesz musiał wprowadzić do kalendarza w celu rozliczenia wydatków, więc musi ona być liczbą nieparzystą.

Ze względu na to, że błąd w kalendarzu pewnie jeszcze przez długie lata nie zostanie poprawiony, a sieć dróg w Bajtocji będzie prawdopodobnie ulegać wielokrotnym przebudowom, postanowiłeś napisać program, który będzie Ci pomagał w takich sytuacjach w przyszłości.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis mapy Bajtocji,
• wyznaczy długość najkrótszej trasy nieparzystej długości między Bajtogrodem a Bitowicami lub stwierdzi, że taka trasa nie istnieje,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem i oznaczające liczbę miast i liczbę dróg w Bajtocji. Miasta są ponumerowane od do ; Bajtogród ma numer , a Bitowice - numer .

Kolejne wierszy przedstawia sieć dróg Bajtocji. Każdy z nich zawiera trzy liczby całkowite pooddzielane pojedynczymi odstępami , , (, , ), oznaczające, że między miastami o numerach i prowadzi dwukierunkowa droga o długości .

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą - długość najkrótszej trasy nieparzystej długości między Bajtogrodem a Bitowicami. Wyznaczona trasa może odwiedzać pewne miasta i drogi wielokrotnie. Zmiany kierunku jazdy na trasie (w tym zawracanie) mogą następować jedynie w miastach. Jeśli poszukiwana trasa nie istnieje, należy wypisać .

Przykład

Dla danych wejściowych:

6 7
1 2 1
2 6 1
1 3 1
5 6 1
3 5 2
3 4 1
5 4 4

poprawną odpowiedzią jest:

7

Autor zadania: Marcin Pilipczuk.