BOJ 1916

[Merrychristmasyo]

import sys
from collections import deque

메모리 초과

input = sys.stdin.readline

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]

for _ in range(m):
a, b, cost = map(int, input().split())
graph[a].append([b, cost])

start, end = map(int, input().split())

def bfs(start):
min_cost = 1e7
q = deque()
q.append([start, 0])
while q:
cur_v, cur_cost = q.popleft()
if cur_v == end and cur_cost < min_cost:
min_cost = cur_cost
for v, c in graph[cur_v]:
q.append([v, cur_cost+c])

return min_cost

print(bfs(start))