Widest Path

We are given a graph that represents the connections between nodes in a computer network. The weight of an edge is the bandwidth of the connection between the two nodes it joins. To transmit data efficiently between two nodes, we want a path with wide bandwidth. The bandwidth of a path is the minimum edge weight along that path. The widest path problem asks for the path between two nodes whose bandwidth is as large as possible.

For example, in Figure 1 the widest path from node 1 to node 4 has bandwidth 25 and passes through node 3 and node 2. The widest path from node 6 to node 3 has bandwidth 30 and passes through node 5.

Figure 1. Example of a computer network

Given two nodes of a graph, write a program that determines the bandwidth of the widest path between them.

The input is read from standard input.

The first line contains the number of test cases $T$.

Each test case begins with a line of four integers $n$, $m$, $s$, and $t$ describing a connected graph, where $n$ ($2 \le n \le 1{,}000$) is the number of nodes and $m$ ($1 \le m \le n(n-1)/2$) is the number of edges. Nodes are numbered from $1$ to $n$, and $s$ and $t$ ($s \ne t$) are the two nodes whose widest path you must report.

Each of the next $m$ lines contains three integers $u$, $v$, and $b$ ($1 \le b \le 10^5$), describing an edge between nodes $u$ and $v$ with bandwidth $b$.

The output is written to standard output. For each test case, print exactly one line containing the bandwidth of the widest path between nodes $s$ and $t$.