#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>

#define pb push_back

using namespace std;

struct link{
	int v, w;
};

struct node{
	int x, d;
	
	bool operator<(const node k)const{
		return x>k.d;
	}
}x;

int n, r, ans=1e9;
int dist_1[5005], dist_2[5005], u[100005], v[100005], w[100005];
bool vis_1[5005], vis_2[5005];
priority_queue<node>q;
vector<link>g[5005];

void add(int u, int v, int w){
	g[u].pb({v,w});
	g[v].pb({u,w});
}

int main(){
	memset(dist_1, 0x3f, sizeof(dist_1));
	memset(dist_2, 0x3f, sizeof(dist_2));
	
	scanf("%d%d", &n, &r);
	for(int i=1; i<=r; i++){
		scanf("%d%d%d", &u[i], &v[i], &w[i]);
		add(u[i], v[i], w[i]);
	}
	
	q.push({1,0});
	dist_1[1]=0;
	while(!q.empty()){
		x=q.top(); q.pop();
		
		if(vis_1[x.x])continue;
		vis_1[x.x]=1;
		
		for(auto i:g[x.x]){
			if(dist_1[x.x]+i.w<dist_1[i.v]){
				dist_1[i.v]=dist_1[x.x]+i.w;
				q.push({i.v,dist_1[x.x]+i.w});
			}
		}
	}
	
	q.push({n,0});
	dist_2[n]=0;
	while(!q.empty()){
		x=q.top(); q.pop();
		
		if(vis_2[x.x])continue;
		vis_2[x.x]=1;
		
		for(auto i:g[x.x]){
			if(dist_2[x.x]+i.w<dist_2[i.v]){
				dist_2[i.v]=dist_2[x.x]+i.w;
				q.push({i.v,dist_2[x.x]+i.w});
			}
		}
	}
	
	for(int i=1; i<=r; i++){
		if(dist_1[u[i]]+w[i]+dist_2[v[i]]>dist_1[n])
			ans=min(ans, dist_1[u[i]]+w[i]+dist_2[v[i]]);
		
		if(dist_1[v[i]]+w[i]+dist_2[u[i]]>dist_1[n])
			ans=min(ans, dist_1[v[i]]+w[i]+dist_2[u[i]]);
	}
	
	printf("%d", ans);
	return 0;
}