Алекс должен пройти из зала s в зал t научного центра. Есть n залов и m двусторонних переходов. Каждый переход занимает одну минуту.
Часть переходов открыта, а часть закрыта. У Алекса есть одноразовый электронный пропуск: он позволяет один раз пройти по одному закрытому переходу. После использования пропуск исчезает, а сам переход остаётся закрытым. По открытым переходам можно ходить без пропуска.
Найдите минимальное время пути. Использовать пропуск необязательно. Если добраться до цели невозможно, выведите −1.
Входные данные
Первая строка содержит целые числа n, m, s, t (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000, 1 ≤ s, t ≤ n). Старт и финиш могут совпадать.
Следующие m строк содержат u, v, c (1 ≤ u, v ≤ n, u ≠ v). При c = 0 переход открыт, при c = 1 — закрыт. Между парой залов не более одного перехода.
Выходные данные
Выведите минимальное время в минутах либо −1, если допустимого маршрута нет.
Пояснения к примерам
Пример 1. Нужно идти 1 → 2 → 3 → 4 → 5 и использовать пропуск в конце. Быстрый переход 1 → 3 потратил бы пропуск слишком рано.
Пример 2. Чтобы пройти этот маршрут, понадобились бы два пропуска.
| № | Входные данные | Выходные данные |
|
1
|
5 5 1 5
1 3 1
1 2 0
2 3 0
3 4 0
4 5 1
|
4
|
|
2
|
3 2 1 3
1 2 1
2 3 1
|
-1
|