轻轻松松
//
//
//
#pragma GCC target ("avx")
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
using namespace __gnu_cxx;
using ll = long long;
typedef pair<int, int> PII;
const int N = 150010;
int n,m;
int e[N],ne[N],h[N],w[N],idx;//邻接表
bool st[N];
int d[N];//存最短路径
void add(int a,int b,int c){
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int Dijkstra(){
memset(d, 0x3f, sizeof d);
d[1]=0;
priority_queue<PII, vector<PII>, greater<PII>> p;
p.push({0,1});//距离0,编号1
while (p.size())
{
auto t = p.top();
p.pop();
int distance = t.x, id = t.y;
if(st[id]) continue;
st[id] = true;
for(int i=h[id]; i != -1 ; i=ne[i]){
int j = e[i];
if(d[j] > distance + w[i]){
d[j] = distance + w[i];
p.push({d[j],j});
}
}
}
if(d[n] == INF) return -1;
return d[n];
}
signed main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
memset(h,-1, sizeof h);
cin>>n>>m;
while (m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
cout<<Dijkstra()<<endl;
return 0;
}