Задачі
Поиск в ширину 0-1-2
Поиск в ширину 0-1-2
Задан неориентированный граф. Вес его ребер может принимать только значения 0, 1 или 2. Найдите кратчайшее расстояние между вершинами s и d.
Вхідні дані
Первая строка содержит четыре целых числа: количество вершин n, количество ребер m (n, m ≤ 10^5
) и номера вершин s и d (1 ≤ s, d ≤ n). Каждая из следующих m строк содержит три целых числа a, b и w задающих неориентированное ребро (a, b) весом w (0 ≤ w ≤ 2).
Вихідні дані
Выведите кратчайший путь между вершинами s и d.
Приклад
Вхідні дані #1
5 5 1 4 1 2 1 2 3 0 3 4 2 1 5 2 4 5 2
Вихідні дані #1
3