Ивана и Сергея пригласили к участию в областной олимпиаде по информатике. Поскольку они проживают в разных населенных пунктах, Иван предложил воспользоваться службой такси, чтобы добраться до места проведения олимпиады.

Такси выезжает из пункта А, где проживает Иван, и направляется в пункт В, забирая Сергея, и дальше едет к месту проведения олимпиады (в пункт С).

Зная длины дорог между населенными пунктами области и стоимость проезда одного километра на такси, посчитайте на сколько больше денег потратил на поездку Иван, заезжая за Сергеем, чем следуя сразу к месту проведения олимпиады.

Известно, что такси всегда выбирает самый короткий из существующих маршрутов.

Входные данные

В первой строке записано пять чисел - четыре целых и одно действительное:

n – количество населенных пунктов,

A – населенный пункт, где проживает Иван,

B – населенный пункт, где проживает Сергей,

С – населенный пункт, где проходит олимпиада,

d – стоимость проезда 1 километра на такси. 

Следующая строка содержит количество дорог m. Каждая из следующих m строк описывает дорогу - два целых числа (номера населенных пунктов, которые соединяет дорога) и действительное число - длина соответствующей дороги в километрах.

Все целые числа натуральные и не больше 100.

Выходные данные

Выведите действительное число - сумму, на которую пришлось заплатить больше, заезжая за Сергеем или -1, если из пункта А не существует маршрута до населенного пункта, где проживает Сергей, или из пункта А не существует маршрута к месту проведения олимпиады.