가장 넓은 경로

컴퓨터 네트워크에서 노드 사이의 연결을 나타내는 그래프가 주어진다. 간선의 가중치는 두 노드를 잇는 연결의 대역폭을 뜻한다. 네트워크에서 두 노드 사이에 데이터를 효율적으로 전송하려면 대역폭이 넓은 경로를 찾는 것이 중요하다. 경로의 대역폭은 그 경로에 포함된 간선들의 가중치 중 최솟값으로 정의한다. 가장 넓은 경로 문제는 두 노드를 잇는 경로 가운데 대역폭이 최대가 되는 경로를 찾는 것이다.

예를 들어 그림 1에서 노드 1에서 노드 4로 가는 가장 넓은 경로의 대역폭은 25이며, 노드 3과 노드 2를 지난다. 노드 6에서 노드 3으로 가는 가장 넓은 경로의 대역폭은 30이고 노드 5를 지난다.

그림 1. 컴퓨터 네트워크의 예시

그래프의 두 노드가 주어졌을 때, 두 노드를 잇는 가장 넓은 경로의 대역폭을 구하는 프로그램을 작성하라.

입력은 표준 입력으로 주어진다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 연결 그래프를 나타내는 네 정수 $n$, $m$, $s$, $t$가 주어진다. $n$ ($2 \le n \le 1{,}000$)은 노드의 개수, $m$ ($1 \le m \le n(n-1)/2$)은 간선의 개수이다. 노드는 $1$번부터 $n$번까지 번호가 매겨지며, $s$와 $t$ ($s \ne t$)는 가장 넓은 경로를 구할 두 노드이다.

이어지는 $m$개의 줄에는 각각 세 정수 $u$, $v$, $b$ ($1 \le b \le 10^5$)가 주어지며, 이는 노드 $u$와 $v$를 잇는 대역폭 $b$의 간선을 뜻한다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 노드 $s$와 $t$를 잇는 가장 넓은 경로의 대역폭을 한 줄에 하나씩 출력한다.