次短路求条

#include<bits/stdc++.h>
#define int long long 
#define N 200010
using namespace std;
inline void read(int &x){
	x=0;char v=getchar();
	while(v<'0'||v>'9') v=getchar();
	while(v>='0'&&v<='9') x=(x<<1)+(x<<3)+(v&15),v=getchar();
}
int n,m,s;
int x,y,z;
struct edge{
	int to;
	int nxt;
	int v;
}e[N];
int h[N],cnt=0;
void add(int from,int to,int cap){
	e[++cnt].to=to;
	e[cnt].v=cap;
	e[cnt].nxt=h[from];
	h[from]=cnt;
}
int u[N],dis[N],dis1[N];
struct node{
	int id,v;
	bool operator < (const node &x) const{
		return v>x.v;
	}
};
void dij(int f){
	priority_queue<node> qu;
	memset(dis,0x3f,sizeof(dis));
	memset(dis1,0x3f,sizeof(dis1));
	node f1;
	f1.id=f,f1.v=0;
	dis[s]=0;
	qu.push(f1);
	while(!qu.empty()){
		int id=qu.top().id;
		qu.pop();
		if(u[id]) continue;
		u[id]=1;
		for(int i=h[id];i;i=e[i].nxt){
			int to=e[i].to;
			if(dis[to]>dis[id]+e[i].v){
				dis1[to]=dis[to];
				dis[to]=dis[id]+e[i].v;
				node f2;
				f2.id=to,f2.v=dis[to];
				qu.push(f2);
			}
			if(dis1[to]>(dis[id]+e[i].v)&&(dis[id]+e[i].v)>dis[to]){
				dis1[to]=dis[id]+e[i].v;
				node f2;
				f2.id=to,f2.v=dis1[to];
				qu.push(f2);
			}
		}
		
	}
}
signed main(){
	read(n),read(m);
	s=1;
//	read({n,m,s});
	for(int i=1;i<=m;i++){
		read(x),read(y),read(z);
		add(x,y,z);
		add(y,x,z);
	}
	dij(s);
	cout<<dis1[n]<<endl;
//	cout<<dis1[n];
	return 0;
}
/*
4 4
1 2 100
2 4 200
2 3 250
3 4 100
*/
/*
5 10
1 2 1982
2 3 3963
3 4 2046
3 5 1353
4 2 1370
4 1 2192
5 3 2898
4 3 1395
4 1 3722
3 2 4596
*/