[白俊]1916回取得最小費用

import heapq
import sys
input=sys.stdin.readline
n=int(input())
m=int(input())
INF=int(1e9)
graph=[[] for _ in range(n+1)]
for i in range(m):
    a,b,c=map(int,input().split())
    graph[a].append((b,c))
distance=[INF]*(n+1)
start,end=map(int,input().split())


def dijckstra(start):
    q=[]
    heapq.heappush(q,(0,start))
    distance[start]=0
    while q:
        dist,now=heapq.heappop(q)
        if distance[now]<dist:
            continue
        for i in graph[now]:
            cost=dist+i[1]
            if cost<distance[i[0]]:
                distance[i[0]]=cost
                heapq.heappush(q,(cost,i[0]))



dijckstra(start)
print(distance[end])