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.

Input

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.

Output

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.