模板代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
vector<pair<int,int>>a[N];
int dis[N],vis[N];
int n,m;
void spfa(){
for(int i=1;i<=n;i++)dis[i]=0x3f;
queue<int>q;
dis[1]=0;
q.push(1);
vis[1]=1;
while(q.size()){
int t=q.front();
q.pop();
vis[t]=0;
for(auto c:a[t]){
int v=c.first;
int w=c.second;
if(dis[v]>dis[t]+w){
dis[v]=dis[t]+w;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
a[u].push_back({v,w});
}
spfa();
cout<<dis[n];
return 0;
}