#include<bits/stdc++.h>
#define R 200010
#define N 5010
using namespace std;
struct edge{
	int to,val,nxt;
}a1[R],a2[R];
const int INF=99999999;
int n,r,cnt1,cnt2,dis1[N],dis2[N],head1[N],head2[N],vis[N];
bool used[R];
int add1(int from,int to,int val){
	a1[++cnt1].nxt=head1[from];
	head1[from]=cnt1;
	a1[cnt1].val=val;
	a1[cnt1].to=to;
}
int add2(int from,int to,int val){
	a2[++cnt2].nxt=head2[from];
	head2[from]=cnt2;
	a2[cnt2].val=val;
	a2[cnt2].to=to;
}
void dij1(){
	memset(dis1,0x7f,sizeof(dis1));
	memset(vis,0,sizeof(vis));
	dis1[1]=0;
	for(int i=1;i<=n-1;i++){
		int k=1,mn=INF;
		for(int j=1;j<=n;j++){
			if(dis1[j]<mn&&vis[j]==0){
				mn=dis1[j];
				k=j;
			}
		}
		vis[k]=1;
		for(int j=head1[k];j!=-1;j=a1[j].nxt){
			if(dis1[a1[j].to]>dis1[k]+a1[j].val){
				dis1[a1[j].to]=dis1[k]+a1[j].val;
			}
		}
	}
}
void dij2(){
	memset(dis2,0x7f,sizeof(dis2));
	memset(vis,0,sizeof(vis));
	dis2[n]=0;
	for(int i=1;i<=n-1;i++){
		int k=1,mn=INF;
		for(int j=1;j<=n;j++){
			if(dis2[j]<mn&&vis[j]==0){
				mn=dis2[j];
				k=j;
			}
		}
		vis[k]=1;
		int pre=0;
		for(int j=head2[k];j!=-1;j=a2[j].nxt){
			if(dis2[a2[j].to]>dis2[k]+a2[j].val){
				dis2[a2[j].to]=dis2[k]+a2[j].val;
				used[pre]=0;
				pre=j;
				used[pre]=1;
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&r);
	memset(head1,-1,sizeof(head1));
	memset(head2,-1,sizeof(head2));
	for(int i=1;i<=r;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add1(u,v,w);
		add2(v,u,w);
	}
	dij1();
	dij2();
	int ans=INF;
	for(int i=1;i<=n;i++){
		for(int j=head1[i];j!=-1;j=a1[j].nxt){
			if(used[j]==0){
				ans=min(ans,dis1[i]+a1[j].val+dis2[a1[j].to]);	
			}
		}
	}
	int mn=INF;
	for(int i=1;i<=n;i++){
		for(int j=head1[i];j!=-1;j=a1[j].nxt){
			if(used[j]==1){
				mn=min(mn,a1[j].val);		
			}
		}
	}
	ans=min(ans,dis1[n]+2*mn);
	printf("%d\n",ans);
	return 0;
}