Івана та Сергія запросили до участі в обласній олімпіаді з інформатики. Оскільки вони проживають у різних населених пунктах, Іван запропонував скористатися службою таксі, щоб дістатися до місця проведення олімпіади.

Таксі виїжджає з пункту А, де проживає Іван, прямує до пункту В, забираючи Сергія і далі їде до місця проведення олімпіади (пункт С).

Знаючи довжини доріг між населеними пунктами області та вартість проїзду одного кілометру на таксі, порахуйте на скільки більше грошей витратив на поїздку Іван, заїжджаючи за Сергієм, ніж прямуючи одразу до місця проведення олімпіади.

Відомо, що таксі завжди вибирає найкоротший з існуючих маршрутів.

Вхідні дані

В першому рядку записано п'ять чисел - чотири цілих та одне дійсне:

n – кількість населених пунктів,

A – населений пункт, де проживає Іван,

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

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

d – вартість проїзду 1 кілометру на таксі. 

Наступний рядок містить кількість доріг m. Кожен з наступних m рядків описує дорогу – два цілих числа (номери населених пунктів, які сполучає дорога) та дійсне число - довжина відповідної дороги в кілометрах.

Усі цілі числа натуральні та не більші 100.

Вихідні дані

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