eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Поиск в ширину 0-1-2

Поиск в ширину 0-1-2

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Задан неориентированный граф. Вес его ребер может принимать только значения 0, 1 или 2. Найдите кратчайшее расстояние между вершинами s и d.

Вхідні дані

Первая строка содержит четыре целых числа: количество вершин n, количество ребер m (n, m10^5) и номера вершин s и d (1s, dn). Каждая из следующих m строк содержит три целых числа a, b и w задающих неориентированное ребро (a, b) весом w (0w2).

Вихідні дані

Выведите кратчайший путь между вершинами s и d.

prb10058.gif

Приклад

Вхідні дані #1
5 5 1 4
1 2 1
2 3 0
3 4 2
1 5 2
4 5 2
Вихідні дані #1
3
Автор Михаил Медведев