폭설이 내린 산간 지역에서 구조대가 마을 \(s\) 에서 마을 \(t\) 까지 이동하려 한다. 각 도로에는 제설 작업 정도를 나타내는 안전도 가 매겨져 있는데, 값이 높을수록 더 안전한 도로이다.

어떤 경로를 택하든, 그 경로의 안전도는 경로에 포함된 도로들의 안전도 중 가장 낮은 값 으로 정해진다(가장 위험한 구간이 경로 전체의 안전도를 결정한다). 구조대는 가능한 모든 경로 중에서 경로의 안전도(최소 안전도)가 가장 커지는 경로를 택하고 싶다.

\(s\) 에서 \(t\) 까지 갈 때 얻을 수 있는 경로 안전도의 최댓값, 즉 모든 경로에 대해 (그 경로의 최소 안전 도로)를 구한 뒤 그 중 최댓값 을 출력하여라. \(s\) 에서 \(t\) 로 도달할 수 없으면 \(-1\) 을 출력한다.

\(2 \le n \le 100{,}000\), \(1 \le m \le 200{,}000\), \(1 \le w \le 10^9\), \(s \ne t\)

첫째 줄에 마을의 수 \(n\) 과 도로의 수 \(m\) 이 주어진다. (\(2 \le n \le 100{,}000\), \(1 \le m \le 200{,}000\))

다음 \(m\) 개의 줄에 세 정수 \(u\ v\ w\) 가 주어지며, 마을 \(u\) 와 \(v\) 를 잇는 안전도 \(w\) 의 양방향 도로를 의미한다. (\(1 \le u, v \le n\), \(u \ne v\), \(1 \le w \le 10^9\))

마지막 줄에 출발 마을 \(s\) 와 도착 마을 \(t\) 가 주어진다. (\(1 \le s, t \le n\), \(s \ne t\))

경로 안전도(최소 안전 도로)의 최댓값을 한 줄에 출력한다. \(t\) 에 도달할 수 없으면 \(-1\) 을 출력한다.

riseoj 작성

출처 Original