Not so long ago, Domin ordered a specific condition for one of the tasks in the online store, and is now expecting its delivery by mail. Domin lives in a country consisting of n cities. Between some of the cities u and v there is a two-way mail communication line that works only on the w-th day of the week (all in all there are 7 days in a week). Also, delivery can be made from any city to any other city (possibly through several other cities). The parcel can be sent in the morning from one city through an open communication channel and arrive in another in the evening, or be kept in the post office for several days until the communication starts working.
An important contest is coming up, so Domin wonders when he could add a new task for the participants. Help him and find the minimum number of days required to deliver the package from the warehouse of conditions to Domin. Domin starts expecting the package from the first day of the week, and the next morning after the package arrives in his city, he immediately runs to the post office to pick it up.
The first line contains 4 numbers: n, m (2 ≤ n ≤ 105, 
) — the number of cities and posts, s and k (1 ≤ s, k ≤ n and s ≠ k) — a city with a warehouse and the city where Domin lives.
The next m lines describe mail messages, each with three numbers: u, v, w (1 ≤ u, v ≤ n, u ≠ v and 1 ≤ w ≤ 7) — the numbers of the cities between which there is a communication and the day on which the mail communication works between the cities u and v.
In a single line type the minimum number of days of expecting the parcel.
5 5 1 5
1 2 1
2 3 2
3 4 3
4 5 4
1 5 5
4
In the first example, the answer is 4 days, as the parcel, after travelling along the path 1 - 2 - 3 - 4 - 5, will arrive by the evening of the fourth day of the week and Domin will take it on the fifth day. And if it is sent directly, then it will arrive by the evening of the fifth day, that is, it will take 5 days to expect it.
