仅供参考

import heapq
INF = 0x3f3f3f3f
N = 1000000

e = [0] * N
idx = 0
ne = [0] * N
w = [0] * N
h = [-1] * N
n, m = map(int, input().split())

def add(a, b, c):
    global e, w, ne ,h, idx
    e[idx] = b
    w[idx] = c
    ne[idx] = h[a]
    h[a]= idx
    idx += 1

while m:
     m -= 1
     a, b, c = map(int, input().split())
     add(a, b, c)

def dijkstra():
    st = [False] * N
    dist = [INF] * N
    dist[1] = 0
    hp = []
    heapq.heappush(hp, (0, 1))

    while len(hp):
        t = heapq.heappop(hp)
        cur = t[1]; dis = t[0]

        if st[cur]: continue
        st[cur] = True

        i = h[cur]
        while ~i:
            j = e[i]
            if dist[j] > dist[cur] + w[i]: 
                dist[j] = dist[cur] + w[i]
                heapq.heappush(hp, (dist[j], j))
            i = ne[i]

    return -1 if dist[n] == INF else dist[n]

print(dijkstra())