Minimizing Maximum Congestion

After work, Xiao Ming's mom hears from neighbors that he has been forcibly taken by a group of strangers and placed into a police car. Her experience tells her that Xiao Ming has been taken to district \(t\), while she is currently in district \(s\).

The city has \(m\) avenues connecting \(n\) districts. Each avenue connects two districts and is assigned a congestion value. To maintain her elegant pace without being disturbed by the crowd, she wants to travel from district \(s\) to district \(t\) along a route that minimizes the maximum congestion encountered along the journey.

In other words, you are asked to find a route from \(s\) to \(t\) such that the maximum congestion value among the avenues in the path is as small as possible. This is a classic bottleneck path problem.

Input: The first line contains four integers \(n, m, s, t\). The following \(m\) lines each contain three integers \(u, v, w\), representing an avenue connecting districts \(u\) and \(v\) with a congestion value \(w\).

Output: Output a single integer representing the minimized maximum congestion value along a valid route from \(s\) to \(t\>.

inputFormat

The first line contains four integers \(n\), \(m\), \(s\), \(t\):

• \(n\): the number of districts,
• \(m\): the number of avenues,
• \(s\): the starting district,
• \(t\): the target district.

Each of the next \(m\) lines contains three integers \(u\), \(v\) and \(w\): an avenue connecting districts \(u\) and \(v\) with a congestion value \(w\).

outputFormat

Output a single integer: the minimized maximum congestion value along a route from district \(s\) to district \(t\).

sample

4 4 1 4
1 2 3
2 4 4
1 3 2
3 4 5

4