W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
Napisz program, który:
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 .
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ć .
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.