[백준] 14284 - 간선 이어가기2 (파이썬)

import heapq
import sys
INF = sys.maxsize
# input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
dis = [INF]*(n+1)
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
s, t = map(int, input().split())
dijkstra(s)
print(dis[t])