In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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:
Task author: Marcin Pilipczuk.