次短路

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
struct node{
	int y;
	long long v;
	node(int _y,long long _v){y=_y;v=_v;};
};
struct P{
	long long dist;
	int id;
	bool operator<(P A)const{
		if (dist==A.dist)
			return id>A.id;
		return dist>A.dist;
	}
};
int n,m;
long long dist[N][2];
vector<node> edge[N];
priority_queue<P> q;
inline long long Dijkstra(){
	memset(dist,127,sizeof(dist));
	q.push({dist[1][0]=0,1});
	while (!q.empty()){
		P t=q.top();q.pop();
		if (t.dist>dist[t.id][1]) continue;
		for (auto i:edge[t.id])
			if (t.dist+i.v<dist[i.y][0]){
				dist[i.y][1]=dist[i.y][0];
				q.push({dist[i.y][0]=t.dist+i.v,i.y});
			}else if (t.dist+i.v<dist[i.y][1]&&
					  t.dist+i.v>dist[i.y][0])
				q.push({dist[i.y][1]=t.dist+i.v,i.y});
	}return dist[n][1];
}
int main(){
	cin>>n>>m;
	while (m--){
		int x,y;long long z;
		cin>>x>>y>>z;
		edge[x].push_back({y,z});
		edge[y].push_back({x,z});
	}cout<<Dijkstra();
	return 0;
}