Таксі#9608
Івана та Сергія запросили взяти участь в обласній олімпіаді з інформатики.
Оскільки вони живуть у різних населених пунктах, Іван запропонував скористатися послугами таксі, щоб дістатися до місця проведення олімпіади.
Таксі виїжджає з пункту , де живе Іван, прямує в пункт , щоб забрати Сергія, а потім їде в пункт , де проводиться олімпіада.
Знаючи відстані між населеними пунктами та вартість одного кілометра поїздки на таксі, визначте, наскільки більше доведеться заплатити, якщо заїхати за Сергієм, ніж їхати прямо до місця проведення олімпіади.
Передбачається, що таксі завжди обирає найкоротший з можливих маршрутів.
У першому рядку дано п'ять чисел: чотири цілих і одне дійсне:
— кількість населених пунктів,
— номер населеного пункту, де живе Іван,
— номер населеного пункту, де живе Сергій,
— номер населеного пункту, де проводиться олімпіада,
— вартість проїзду одного кілометра на таксі.
У другому рядку задано ціле число — кількість доріг.
Далі йдуть рядків, кожен з яких описує одну дорогу: два цілих числа — номери населених пунктів, які вона з'єднує, і одне дійсне число — довжина цієї дороги в кілометрах.
Усі номери населених пунктів – натуральні числа, не більше .
Виведіть одне дійсне число — суму, на яку дорожча була поїздка з заїздом за Сергієм у порівнянні з прямим маршрутом.
Якщо маршруту з пункту до пункту або з пункту до пункту не існує, виведіть .
Приклад 1