Пошук у ширину 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$.

Приклади