이번 문제는 다익스트라 알고리즘을 통해 해결하였다. heapq에 다리의 무게제한을 음수로 바꿔 넣어 최대힙으로 활용하였고, 다익스트라 알고리즘으로 탐색을 진행하여 도착 위치에 해당하는 값을 출력하도록 하였다.

Code

import heapq
n, m = map(int, input().split())
s, e = map(int, input().split())
bridges = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    bridges[a].append((b, c))
    bridges[b].append((a, c))
def to_HB(cur):
    q = []
    heapq.heappush(q, (-1e9, cur))
    golds = [0 for _ in range(n+1)]
    golds[cur] = 1e9
    while q:
        gold, cur = heapq.heappop(q)
        gold = -gold
        if gold < golds[cur]:
            continue
        for nxt, g in bridges[cur]:
            nxt_g = min(g, gold)
            if golds[nxt] < nxt_g:
                golds[nxt] = nxt_g
                heapq.heappush(q, (-nxt_g, nxt))
    return golds[e]
print(to_HB(s))