중량 제한
시간 제한1초메모리 제한128 MB
가중치가 있는 무방향 그래프에서 두 공장 섬 사이 경로 중 병목이 되는 최소 가중치를 최대화하는 값을 구합니다.
문제
섬 N개로 이루어진 나라가 있다. 몇몇 섬 사이에는 양방향 다리가 놓여 있어 차량이 이동할 수 있으며, 각 다리에는 한 번에 지나갈 수 있는 물품의 최대 중량이 정해져 있다.
서로 다른 두 섬에는 공장이 하나씩 있다. 한 공장에서 다른 공장으로 물품을 옮기려고 할 때, 이동 경로에 포함된 모든 다리의 중량 제한을 넘지 않아야 한다. 제한보다 무거운 물품이 지나가면 다리가 무너진다.
두 공장 사이에서 한 번의 이동으로 옮길 수 있는 물품 중량의 최댓값을 구하시오.
입력
첫째 줄에 섬의 개수 N과 다리의 개수 M이 주어진다. 2 <= N <= 10,000, 1 <= M <= 100,000이다.
다음 M개의 줄에는 다리 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량 제한이 C인 양방향 다리가 있다는 뜻이다. 1 <= A, B <= N, 1 <= C <= 1,000,000,000이며, 같은 두 섬 사이에 여러 개의 다리가 있을 수 있다.
마지막 줄에는 두 공장이 있는 서로 다른 섬의 번호가 주어진다. 두 공장 사이를 잇는 경로는 항상 존재한다.
출력
두 공장 사이에서 한 번에 옮길 수 있는 물품 중량의 최댓값을 첫째 줄에 출력한다.