题目：

 

代码：

from heapq import *
#堆优化版本的最短路算法（dijkstra）
N=150010
h=[-1 for _ in range(N)]
e=[-1 for _ in range(N)]
ne=[-1 for _ in range(N)]
w=[-1 for _ in range(N)]
idx=0
st=[False for _ in range(N)]
dist=[float('inf') for _ in range(N)]def add(a,b,c):global idxe[idx]=bw[idx]=cne[idx]=h[a]h[a]=idxidx+=1def dijkstra():dist[1]=0heap=[]heappush(heap,(0,1))while heap:d,ver=heappop(heap)if(st[ver]) :continuest[ver]=Truei=h[ver]while i!=-1:j=e[i]if dist[j]> d + w[i]:dist[j]=d+w[i]heappush(heap,(dist[j],j))i=ne[i]if dist[n] == float('inf'):return -1else: return dist[n]if __name__== "__main__":n,m=map(int, input().split())while m:m-=1a,b,c=map(int,input().split())add(a,b,c)print(dijkstra())