#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define int long long
const int N=3e5+10;
int dp[N][2];
vector<pair<int,int> > v[N+10];
void solve() {
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++) {
		int x,y,w;cin>>x>>y>>w;
		v[x].push_back({y,w});
		v[y].push_back({x,w});
	}
	set<pair<int,int> > s;
	int minn=0x3f;
	s.insert({0,1});
	dp[1][0]=0;
	dp[1][1]=0;
	while(s.size()) {
		auto t=s.begin();
		s.erase(t);
		pair<int,int> p;
		p=*t;
		int x=p.second;
		
		for(auto y:v[x]) {
			int cnt=y.second;
			int yy=y.first,xz=dp[x][1],yz=dp[x][0];//if(x==5) cout<<"P="<<p.first<<endl;
			if(cnt>xz){
				yz=xz;
				xz=cnt;
			}else if(cnt>yz){
				yz=cnt;
			}
			if(dp[yy][1]==0&&dp[yy][0]==0){
				dp[yy][1]=xz;
				dp[yy][0]=yz;
			}else{
				if(dp[yy][1]+dp[yy][0]<=xz+yz)continue;
				else {
					dp[yy][1]=xz;
					dp[yy][0]=yz;
				}
			}
			dp[yy][1]=xz;
			dp[yy][0]=yz;
		//	if(x==5&&yy==8) cout<<xz<<' '<<yz<<endl;
			if(yy==n) {
				minn=min(minn,dp[y.first][1]+dp[y.first][0]);
				continue;
			}
			s.insert({dp[y.first][1]+dp[y.first][0],y.first});
		}
	}
	cout<<minn<<endl;
}
signed main()
{
	int t=1;
	while(t--) solve();
	return 0;
}
/*6 7
1 2 1
1 5 2
1 6 4
2 3 2
3 4 1
4 6 1
5 6 2*/