Назар та Юля знаходяться на різних полонинах Карпат і збираються повернутися на базу. Вони пробують скласти такий маршрут, щоб мінімізувати витрати енергії - харчі обмежені і запасу калорій немає.

Назар витрачає ~B~ одиниць енергії на перехід з одного пункту до сусіднього, а Юля витрачає ~E~ одиниць. Якщо Назар та Юля випадково опиняться в одному пункті, то Назар зможе понести Юлю на руках (якщо це буде енергетично вигідно), витративши ~P~ одиниць енергії для переміщення у сусідній пункт (~P~ може бути меншим ніж ~B + E~).

За заданим ~B~, ~E~, ~P~ і розташуванням пунктів, обчисліть мінімальну кількість енергії, яка буде потрібна Назару та Юлі щоб повернутися на базу.

Формат вхідних даних

Перший рядок містить додатні числа ~B~, ~E~, ~P~, ~N~, ~M~, які не перевищують 40000. ~N~ - кількість пунктів, пронумерованих від 1 до ~N~, (~3 \le N~). ~M~ - кількість шляхів між пунктами. Назар та Юля знаходяться на початку в пунктах 1 і 2 відповідно. База розташована в пункті ~N~.

Кожен з наступних ~M~ рядків описує шлях між пунктами. Шляхи двонаправлені. Завжди існує шлях від пункту 1 до пункту ~N~ і від пункту 2 до пункту ~N~.

Формат вихідних даних

Вивести одне число - мінімальну сумарну енергію, яку витратять Назар та Юля для повернення на базу.

Приклад вхідних даних

4 4 5 8 8 1 4 2 3 3 4 4 7 2 5 5 6 6 8 7 8

Приклад вихідних даних

22