====== 군사 이동 ======

===== 풀이 =====
  * 문제 설명이 살짝 헷갈릴 수 있는데, c에서 v로 가는 경로중에서 가장 좁은 길의 너비가 최대가 되는 경로를 찾으라는 뜻이다
  * 엣지들을 내림차순으로 정렬한 뒤, c와 v가 연결될때까지 하나씩 추가해보다가 연결되는 순간 추가된 엣지를 출력하면 된다. 연결 여부는 [[ps:Disjoint Set]]을 사용한다. 엣지를 정렬하고 하나씩 추가하면서 disjoint set을 업데이트 하는 것은 크루스칼 알고리즘의 아이디어와도 살짝 비슷한 느낌이다.
  * 지점의 갯수가 n, 길의 갯수가 m일때, 길을 정렬하는데에 O(mlogm)이 걸리고, 정렬된 길들 최대 m개 추가하면서 연결성을 확인하는 데에는 O(m*α(n))이 걸린다. 총 시간 복잡도는 O(m*(α(n)+logm))


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11085. 군사 이동".

- Problem link: https://www.acmicpc.net/problem/11085
- Solution link: http://www.teferi.net/ps/problems/boj/11085

Tags: [DisjointSet]
"""

import sys
from teflib import disjointset


def main():
    p, w = [int(x) for x in sys.stdin.readline().split()]
    c, v = [int(x) for x in sys.stdin.readline().split()]
    dsu = disjointset.DisjointSet(p)
    walkways = []
    for _ in range(w):
        w_start, w_end, w_width = [int(x) for x in sys.stdin.readline().split()]
        walkways.append((w_width, w_start, w_end))
    walkways.sort(reverse=True)
    for w_width, w_start, w_end in walkways:
        dsu.union(w_start, w_end)
        if dsu.find(c) == dsu.find(v):
            print(w_width)
            break


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:disjointset#DisjointSet|teflib.disjointset.DisjointSet]]

{{tag>BOJ ps:problems:boj:골드_3}}