В стране есть n аэропортов, между некоторыми парами аэропортов выполняются прямые авиарейсы. Каждый рейс имеет известную стоимость. Все рейсы двусторонние: если можно долететь из аэропорта u в аэропорт v за w, то и обратно тоже можно долететь за ту же стоимость.

Нужно организовать перелёт из аэропорта s в аэропорт t, при этом маршрут обязательно должен проходить через главный аэропорт v, где совершается обязательная пересадка.

Иными словами, требуется найти минимальную стоимость маршрута s -> v -> t. Главный аэропорт может совпадать с аэропортом вылета или прилёта.

Если такого маршрута не существует, выведите -1.

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

В первой строке заданы пять целых чисел n, m, s, v, t — количество аэропортов, количество прямых рейсов, аэропорт вылета, главный аэропорт и аэропорт назначения.

В следующих m строках заданы рейсы в формате a b w, где a и b — аэропорты, между которыми есть прямой рейс, а w — его стоимость.

Ввод осуществляется через стандартный ввод.

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

Выведите одно целое число — минимальную стоимость маршрута из s в t с обязательной пересадкой в аэропорту v, либо -1, если такого маршрута не существует.

Вывод осуществляется через стандартный вывод.

Ограничения

• 1 <= n <= 100000
• 0 <= m <= 300000
• 1 <= s, v, t <= n
• 1 <= a, b <= n
• 0 <= w <= 1000000

Примеры

Пример 1

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

3 2 1 2 3
1 2 5
2 3 7

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

12

Пример 2

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

4 2 1 2 4
1 2 3
3 4 8

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

-1