由于不会次短路所以用 k 短路的代码改了改。。。不吸氧 TLE，吸氧 MLE。。。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define fi first
#define se second
using namespace std;
const int N=5010;
ll n,m,k=2,u,v,w,dis[N];
vector<pli>g[N];
bool vis[N];
priority_queue<pli,vector<pli>,greater<pli>>q;
void bfs(){
	q.push({0,1});//first 当前dis1[i] disN最小值出队
	while(q.size()){
		auto now=q.top();
		q.pop();
		if(now.se==n){
			--k;
			if(!k){
				cout<<now.fi;
				return; 
			}
		}
		for(auto i:g[now.se]){
			//不更新直接放q里
            q.push({i.fi+now.fi,i.se});
		}
	}                           
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		scanf("%d%d%lld",&u,&v,&w);
		g[u].pb({w,v});
		g[v].pb({w,u});
	}
	bfs();
	return 0;
}