세부 - BOJ

세부 - BOJ

from collections import deque

N, M = map(int, input().split())
s, e = map(int, input().split())
d = [[] for _ in range(N+1)]


def bfs(c):
    q = deque()
    q.append(s)
    visit = [False] * (N + 1)
    visit[s] = True
    while q:
        x = q.popleft()
        for y, k in d[x]:
            if not visit[y] and k >= c:
                visit[y] = True
                q.append(y)
    return visit[e]


start = 1000000
end = 1

for _ in range(M):
    h1, h2, k = map(int, input().split())
    d[h1].append((h2, k))
    d[h2].append((h1, k))
    start = min(start, k)
    end = max(end, k)

if not d[s] or not d[e]:
    print(0)
    exit(0)

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

print(ret)