*1939-중량제한 (python, 파이썬)

- 포인트:
  - 이동 가능한 중량: 최소 중량 ~ 최대 중량 사이에 있다
  - 이동 가능한 중량을 찾기 위해서 이진 탐색을 사용한다
    - 이진 탐색을 쓰는 이유: 제한된 시간 내에 최적의 값을 찾아야 하는 문제이기 때문이다.
        이진 탐색의 시간 복잡도가 O(log n)이라는 점은 매우 중요한 포인트이다! 최적의 값을 찾도록 도와주는 게
        이진 탐색이라는 것을 알았기 때문에 이제 중간 값(mid=현재 중량 값)을 찾아가며 적용시키면 된다!
    - 정답을 무조건 최대 중량으로 잡지 않는 이유: 
        먼저는 도착지점까지 갈 수 있는지를 고려해야 하는데(bfs), 이때 최대 중량을 싣는 것이 불가능할 수 있기 때문
        그래서 경로상으로 문제없이 도착할 수 있는 최적의 중량을 탐색하는 것이 동반됨 (탐색이 중요!)
        - 이동 가능할 때: 중량을 결과로 대입, 사용가능한 최소 중량의 값을 (현재 중량+1)로 대입
        - 이동 불가능할 때: 사용가능한 최대 중량의 값을 (현재 중량-1)로 대입

from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]

def bfs(c):
    queue = deque([start_node])
    visited = [False] * (n + 1)
    visited[start_node] = True
    while queue:
        x = queue.popleft()
        for y, weight in adj[x]:
            if not visited[y] and weight >= c:
                visited[y] = True
                queue.append(y)
    return visited[end_node]

start = 1_000_000_000
end = 1

for _ in range(m):
    x, y, weight = map(int, input().split())
    adj[x].append((y, weight))
    adj[y].append((x, weight))
    start = min(start, weight)
    end = max(end, weight)

start_node, end_node = map(int, input().split())

result = start
while(start <= end):
    mid = (start+end) // 2
    if bfs(mid):
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)