https://www.acwing.com/problem/content/851/
python dijkstra模板
注意点:
初始化时临界矩阵时要记得把没有边的初始化成最大值，写的时候老是忘记

两种写法邻接表和邻接矩阵，稠密图使用临界矩阵，一般的稀疏图使用邻接表

# 邻接矩阵
n, m = (int(x) for x in input().strip().split(' '))
g = [[1<<30 for j in range(n+1)] for i in range(n+1)]
for i in range(1,n+1):
    g[i][i] = 0
for i in range(m):
    a,b,c = (int(x) for x in input().strip().split(' '))
    g[a][b] = min(c,g[a][b])
d = [1<<30 for i in range(n+1)]
v = [0 for i in range(n+1)]
d[1] = 0
for i in range(n):
    x,minlen = -1, 1 << 30
    for j in range(1,n+1):
        if not v[j] and d[j] < minlen:
            x,minlen = j, d[j]
    v[x] = 1
    for j in range(1,n+1):
        if not v[j] and d[j] > d[x] + g[x][j]:
            d[j] = d[x] + g[x][j]
if d[n] == 1<<30:
    print(-1)
else:
    print(d[n])

# 邻接表
n, m = (int(x) for x in input().strip().split(' '))
g = [[] for i in range(n+1)]
for i in range(m):
    a,b,c = (int(x) for x in input().strip().split(' '))
    g[a].append([b,c])
d = [1<<30 for i in range(n+1)]
v = [0 for i in range(n+1)]
d[1] = 0
for i in range(n):
    x,minlen = -1, 1 << 30
    for j in range(1,n+1):
        if not v[j] and d[j] < minlen:
            x,minlen = j, d[j]
    v[x] = 1
    for j in g[x]:
        if not v[j[0]] and d[j[0]] > d[x] + j[1]:
            d[j[0]] = d[x] + j[1]
if d[n] == 1<<30:
    print(-1)
else:
    print(d[n])