#include<bits/stdc++.h>
using namespace std;
struct node{
	long long to,val;
};
vector<node>a[5005];
long long d[5005],s[5005],n,m;
long long flag[5005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(d,0x7f,sizeof d);
	memset(s,0x7f,sizeof s);
	cin>>n>>m;
	for(long long i=1;i<=m;i++){
		long long u,v,w;
		cin>>u>>v>>w;
		a[u].push_back(node{v,w});
		a[v].push_back(node{u,w});
	}
	d[1]=0;
	for(long long i=1;i<=2*n;i++){
		long long t=0;
		for(long long j=1;j<=n;j++){
			if(flag[j]<2&&d[j]<d[t])t=j;
		}
		flag[t]++;
		for(long long j=0;j<a[t].size();j++){
			if(d[t]+a[t][j].val<d[a[t][j].to]){
				s[a[t][j].to]=d[a[t][j].to];
				d[a[t][j].to]=d[t]+a[t][j].val;
			}
			if(d[t]+a[t][j].val<s[a[t][j].to]&&d[t]+a[t][j].val>d[a[t][j].to]){
				s[a[t][j].to]=d[t]+a[t][j].val;
			}
			if(s[t]+a[t][j].val<s[a[t][j].to]){
				s[a[t][j].to]=s[t]+a[t][j].val;
			}
		}
	}
	cout<<s[n];
	return 0;
}