Gold snack sticks on Cebu

Hyebin and Sungi took a trip to an island near Cebu. The island is a set of houses floating on the sea, joined by oak bridges. Sungi arranged a surprise event with the island keeper, who is keeping Hyebin at the event site.

On the day of the event Sungi wants to carry snack sticks made of gold to that site. Every bridge has a weight limit on how much can cross it at once. Throwing away expensive gold on the way would be a waste, so Sungi wants to leave home carrying exactly as many sticks as can reach Hyebin's house in one trip.

Sungi picks any route and may pass through the same house or the same bridge more than once. Whatever route is taken, the smallest weight limit among the bridges on that route decides how much can be carried at once. Given the house numbers and the weight limit of every bridge, find the largest number of gold sticks Sungi can bring to Hyebin.

One gold stick weighs 1, and Sungi's own weight is not counted.

The first line has the number of houses $N$ ($2 \le N \le 100\,000$) and the number of bridges $M$ ($1 \le M \le 300\,000$).

The second line has the number of the house Sungi starts from, $s$, and the number of the house Hyebin is in, $e$. ($1 \le s, e \le N$, $s \ne e$)

Each of the next $M$ lines describes one bridge as a house number $h_1$ ($1 \le h_1 \le N$), a house number $h_2$ ($1 \le h_2 \le N$), and a weight limit $k$ ($1 \le k \le 1\,000\,000$), meaning house $h_1$ and house $h_2$ are joined by a bridge whose weight limit is $k$. A bridge can be crossed in both directions.

Several bridges may join the same pair of houses, and a bridge with $h_1$ equal to $h_2$ may appear.

Print on the first line the largest number of gold sticks that can be carried in one trip from Sungi's house to Hyebin's house. If no route joins the two houses, print 0.

In the first example the best route crosses $1 \to 7$ (limit 4), $7 \to 6$ (limit 4), and $6 \to 5$ (limit 3). The amount this route carries at once is $\min(4, 4, 3) = 3$.