세부 (백준 13905)

 목적지에 도달하는 경로 중에서 최소 가중치를 찾으면 된다. MST를 적용하되 목적지에 도달하는 최대의 길들만 찾아서 

그 중 최소의 값을 찾으면 된다. 

import sys 
import heapq 
input =sys.stdin.readline
n,m = map(int, input().split())
start, end = map(int, input().split())

visited= [0 for i in range(n+1)]
visited[0]  = 1 
gra = [[]for _ in range(n+1)]
for i in range(m):
    a,b,c =map(int ,input().split())
    gra[a].append((b,c))
    gra[b].append((a,c))

ans =int(1e9)
def prim(start):
    global ans 
    q = [[0,start,start]]
    heapq.heapify(q)
    while q :
        cost, now, prev = heapq.heappop(q)
        if visited[now] ==0 :
            visited[now] = prev 
            # ans += ((-1)*cost)
            for nextnode,nextcost in gra[now] :
                if visited[nextnode] ==0 :
                    neg = (-1)*nextcost
                    heapq.heappush(q, (neg, nextnode,now))
prim(start)

if visited[end]==0 :
    print(0)
    exit() 

while True :
    before = visited[end]
    if before == end :
        break
    for a,b in gra[end] :
        if a == before :
            ans = min(ans, b)
    # ans = min(ans, gra[before][end])
    end = before 
    
    
print(ans)