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

Приклади