Такси
Ивана и Сергея пригласили к участию в областной олимпиаде по информатике. Поскольку они проживают в разных населенных пунктах, Иван предложил воспользоваться службой такси, чтобы добраться до места проведения олимпиады.
Такси выезжает из пункта А, где проживает Иван, и направляется в пункт В, забирая Сергея, и дальше едет к месту проведения олимпиады (в пункт С).
Зная длины дорог между населенными пунктами области и стоимость проезда одного километра на такси, посчитайте на сколько больше денег потратил на поездку Иван, заезжая за Сергеем, чем следуя сразу к месту проведения олимпиады.
Известно, что такси всегда выбирает самый короткий из существующих маршрутов.
Входные данные
В первой строке записано пять чисел - четыре целых и одно действительное:
n – количество населенных пунктов,
A – населенный пункт, где проживает Иван,
B – населенный пункт, где проживает Сергей,
С – населенный пункт, где проходит олимпиада,
d – стоимость проезда 1 километра на такси.
Следующая строка содержит количество дорог m. Каждая из следующих m строк описывает дорогу - два целых числа (номера населенных пунктов, которые соединяет дорога) и действительное число - длина соответствующей дороги в километрах.
Все целые числа натуральные и не больше 100.
Выходные данные
Выведите действительное число - сумму, на которую пришлось заплатить больше, заезжая за Сергеем или -1, если из пункта А не существует маршрута до населенного пункта, где проживает Сергей, или из пункта А не существует маршрута к месту проведения олимпиады.
