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

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

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

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

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

Выведите кратчайшее расстояние между вершинами $s$ и $d$.

Примеры