P1396 Rescue

“Knock, knock...” “Water meter inspection!” Turns out it’s the meter inspector. Where can you find such thoughtful door-to-door inspectors these days? Moved to tears, Xiaoming opened the door.

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.

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 a single integer: the minimal possible value of the maximum congestion level along the chosen route.

#### 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