Description

When Mom came home from work, the neighbors said that Xiaoming had been forced into a police car by a group of strangers. With her experience, she inferred that Xiaoming was taken to district $t$, while she herself is in district $s$.

The city has $m$ avenues connecting $n$ districts. Each avenue connects two districts and has a congestion level. Although Xiaoming’s mom is in a hurry, she does not want the crowded flow to disrupt her elegant pace. Please help her plan a route from $s$ to $t$ such that the maximum congestion level among the avenues on the route is minimized.

Input Format

The first line contains four space-separated integers $n$, $m$, $s$, $t$, whose meanings are as described above.

The next $m$ lines each contain three integers $u, v, w$, indicating there is an avenue connecting districts $u$ and $v$ with congestion level $w$.

There may be multiple avenues between two districts.

Output Format

Output a single integer: the minimal possible value of the maximum congestion level along the chosen route.

3 3 1 3
1 2 2
2 3 1
1 3 3

2

Hint

Constraints

• For $30\%$ of the testdata, $n \leq 10$.
• For $60\%$ of the testdata, $n \leq 100$.
• For $100\%$ of the testdata, $1 \leq n \leq 10^4$, $1 \leq m \leq 2 \times 10^4$, $w \leq 10^4$, $1 \leq s, t \leq n$. It is guaranteed that from $s$ one can reach district $t$.

Explanation for Sample 1

Xiaoming’s mom needs to go from point 1 to point 3. An optimal route is 1 -> 2 -> 3.

Translated by ChatGPT 5