favorite We need a little bit of your help to keep things running, click on this banner to learn more

Dijkstra algorithm


Ivan and Sergey were invited to participate in the regional Olympiad in computer science. Since they live in different settlements, Ivan suggested to use a taxi service to get to the venue of the Olympiad.

Taxi leaves from A, where Ivan lives, goes to B, picks up Sergey, and then goes to the venue of the Olympiad (to C).

Knowing the length of the roads between the settlements of the region and the cost of travelling one kilometre by taxi, calculate how much more money Ivan will spend on the trip, stopping to take Sergey, than going straight to the venue of the Olympiad.

It is known that taxi always chooses the shortest from existing routes.


First line contains five numbers - four integers and one real:

n – number of settlements;

A – the settlements where Ivan lives;

B – the settlements where Sergey lives;

С – the venue of the Olympiad;

d – the price of 1 kilometre by taxi. 

Next line contains the number of roads m. Each of the following m lines describes one road - two integers (numbers of the settlements that the road connects) and a real number - the length of the corresponding road in kilometres.

All integers are positive and no more than 100.


Print the real number - the amount of money you have to pay more when coming for Sergey or -1, if from point A there is no route to the settlement where Sergey lives, or from point A there is no route to the venue of the Olympiad.


Time limit 1 second
Memory limit 128 MiB
Input example #1
5 1 2 3 4.25
1 4 2.5
4 2 3
4 5 3
3 5 2
3 4 8
Output example #1
Source 2020 XXXIV regional olympiad in informatics, Zhitomyr