以下部分是代码

#include<bits/stdc++.h>

using namespace std;

int n,m;
struct node{
	int w,id;
	bool operator < (const node &u)const{
		return w>u.w;
	}
};vector<node> g[100010];
struct{int dis,maxdist;}dist[100010];
bool st[100010];

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x;
} 

void dijkstra(){
	dist[1].dis=0;dist[1].maxdist=0;
	priority_queue<node> q;
	q.push({0,1});
	while(q.size()){
		node t=q.top();
		q.pop();
		int dis=t.w,id=t.id;
		if(st[id]) continue;
		st[id]=true;
		for(int i=0;i<g[id].size();++i){
			int j=g[id][i].id;
			if(dist[j].dis+dist[j].maxdist>dist[id].dis+g[id][i].w+max(dist[id].maxdist,g[id][i].w)){
				dist[j].dis=dist[id].dis+g[id][i].w;
				dist[j].maxdist=max(dist[id].maxdist,g[id][i].w);
				q.push({dist[j].dis,j});
			}
		}
	}
	return;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		dist[i].dis=0x3f3f3f3f;
		dist[i].maxdist=0x3f3f3f3f;
		st[i]=false;
	}
	for(int i=0;i<m;++i){
		int u=read(),v=read(),w=read();
		node k;k.id=v;k.w=w;
		g[u].push_back(k);k.id=u;
		g[v].push_back(k);
	}
	dijkstra();
	cout<<dist[n].dis+dist[n].maxdist;
	return 0;
}