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.
Your electronic calendar contains an error - something that programmers call a bug. Due to this bug, even integers cannot be entered into the calendar.
You are planning a business trip from Bytetown to Bitcity. Obviously, you would like to take the shortest path for the trip. After you return, you will have to enter the length of the path to your calendar, so the length needs to be an odd integer.
Taking into consideration that the bug in the calendar will surely remain uncorrected for quite a long time, and that the road system in Byteland will probably be reconstructed multiple times, you decided to write a program that will help you in dealing with similar problems in future.
Write a program that:
The first line of input contains two integers and (, ), separated by a single space and denoting the number of cities and the number of roads in Byteland. The cities are numbered from to ; Bytetown has number , whereas Bitcity - number .
The following lines describe the system of roads in Byteland. Each of them contains three space-separated integers , , (, , ) denoting a bidirectional road of length connecting cities with numbers and .
The first and only line of output should contain one integer - the length of the shortest odd-length path from Bytetown to Bitcity. The computed path may visit some cities and roads multiple times. Changes in direction of driving (including turning back) can only be performed in cities. If no such path exists, the correct output is .
For the input data:
6 7 1 2 1 2 6 1 1 3 1 5 6 1 3 5 2 3 4 1 5 4 4
the correct result is:
7
Task author: Marcin Pilipczuk.