Недавно Домин заказал в интернет-магазине условие для одной из задач, и теперь ожидает его доставки по почте. Домин живет в стране, состоящей из n городов, причем между некоторыми городами u и v есть двустороннее почтовое сообщение, которое работает лишь в w-й день недели (всего в неделе 7 дней). Также доставку можно произвести из любого города в любой другой (возможно, через другие города). Посылка может быть отправлена утром из одного города по открытому сообщению и прибыть в другой к вечеру, или пролежать в почтовом отделении несколько дней, пока сообщение не заработает.
Скоро важный контест, поэтому Домину стало интересно, когда он сможет добавить новую задачу. Помогите ему и найдите минимальное количество дней, необходимое для доставки посылки от склада условий до Домина. Домин начинает ожидать посылку с первого дня недели, и на следующее утро после того, когда посылка прибывает в его город, он сразу же бежит на почту забирать её.
В первой строке содержатся 4 числа: n, m (2 ≤ n ≤ 105, 
) — количество городов и сообщений, s и k (1 ≤ s, k ≤ n и s ≠ k) — номер города со складом и город, где живет Домин.
В следующих m строках описываются почтовые сообщения, в каждой три числа: u, v, w (1 ≤ u, v ≤ n, u ≠ v и 1 ≤ w ≤ 7) — номера городов, между которыми есть сообщение и день, в который между городами u и v работает почтовое сообщение.
В единственной строке выведите минимальное количество дней ожидания посылки.
5 5 1 5
1 2 1
2 3 2
3 4 3
4 5 4
1 5 5
4
В первом примере ответ 4 дня, так как посылка, пройдя по пути 1 - 2 - 3 - 4 - 5, прибудет к вечеру четвертого дня недели и Домин заберет её утром пятого дня. А если она будет отправлена напрямую, то она прибудет к вечеру пятого дня, и Домин сможет забрать её утром шестого дня, то есть ждать её придется 5 дней.
