В подземном городе есть n залов, соединённых направленными тоннелями. Каждый тоннель позволяет пройти только в одном направлении.

Для каждого тоннеля известен его тип:

• бесплатный, тогда стоимость прохода по нему равна 0;
• платный, тогда стоимость прохода по нему равна 1.

Нужно определить минимальную суммарную стоимость пути из зала s в зал t.

Стоимость пути равна сумме стоимостей всех тоннелей на этом пути. Если добраться из s в t невозможно, выведите -1.

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

В первой строке заданы четыре целых числа n, m, s, t — количество залов, количество тоннелей, начальный зал и конечный зал.

В следующих m строках заданы тоннели в формате u v w, где:

• u — зал, из которого начинается тоннель;
• v — зал, в который ведёт тоннель;
• w — стоимость прохода по тоннелю, равная 0 или 1.

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

Выведите одно целое число — минимальную стоимость пути из s в t, либо -1, если такого пути не существует.

Ограничения

• 1 <= n <= 200000
• 0 <= m <= 300000
• 1 <= s, t <= n
• 1 <= u, v <= n
• w равно 0 или 1
• Возможны тоннели из зала в тот же зал.
• Между одной и той же парой залов может быть несколько тоннелей.

Примеры

Пример 1

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

2 1 1 2
1 2 0

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

0

Пример 2

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

4 4 1 4
1 1 0
2 2 1
1 2 1
2 3 0

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

-1