Highways
A number of cities are connected by a network of highways. Each highway is bidirectional and connects two cities, with a given travel time. What is the shortest time to get from a given city to another given city?
InputEach test case starts with a line containing four integers. The number of cities n (2<=n<=100,000), the number of highways m (1<=m<=80,000), the starting city, and the ending city. Cities are numbered from 1 to n.
Then m lines follow, each describing one highway. The description consists of the two distinct city numbers and the time in minutes to travel along the highway. The time will be between 1 and 1000.
Then m lines follow, each describing one highway. The description consists of the two distinct city numbers and the time in minutes to travel along the highway. The time will be between 1 and 1000.
OutputFor each test case output a single line containing the minimum time it takes to get from the start to the destination. If no connection exists, output -1.
Sample input
4 2 1 4
1 2 5
3 4 5
Sample output-1
Sample Input
4 4 1 4
1 2 5
2 3 5
3 4 5
4 2 6
Sample output11
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.