Baekjoon-1916-최소비용 구하기

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

N = int(input())
M = int(input())

# Dijkstra algorithm
bus_dict = [[] for k in range(N+1)]
for m in range(M):
    s_i, e_i, w_i = map(int, input().split(' '))
    bus_dict[s_i].append((e_i, w_i))

node_from, node_to = map(int, input().split(' '))

dist_dict = [int(1e9) for k in range(N+1)]
dist_dict[node_from] = 0

heap = []
heappush(heap, [0,node_from])
while heap:
    cur_dist, cur_node = heappop(heap)

    if cur_dist > dist_dict[cur_node]:
        continue
    
    for new_node, new_dist in bus_dict[cur_node]:
        dist = cur_dist + new_dist
        if dist < dist_dict[new_node]:
            dist_dict[new_node] = dist
            heappush(heap, [dist, new_node])

print(dist_dict[node_to])