#include <bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
struct edge{
	int to,w;
};
vector<edge> e[maxn],e2[maxn];
int dis[maxn];bool vis[maxn];
void addedge(int u,int v,int w)
{
	e[u].push_back((edge){v,w});
	e[v].push_back((edge){u,w});
	e2[v].push_back((edge){u,w});
	e2[u].push_back((edge){v,w});
}
struct node{
	int s,dis;
	bool operator <(const node &a)const{return dis>a.dis;}
};
void dijkstra(int s)
{
	priority_queue<node> q;
	memset(dis,0,sizeof(dis));
	dis[s]=0;
	q.push((node){s,dis[s]});
	while(q.size())
	{
		int u=q.top().s;q.pop();
		if (vis[u]) continue;
		vis[u]=1;
		for (int i=0;i<e2[u].size();i++)
		{
			int w=e2[u][i].to,v=e2[u][i].w;
			if (v+dis[u]<dis[w])
			{
				dis[w]=v+dis[u];
				q.push((node){w,dis[w]});
			}
		}
	}
}
struct point{
	int v,g,h;
	bool operator <(const point &a)const{return g+h>a.g+a.h;}
};
int ti[maxn];
int astar(int s,int t,int k)
{
	memset(ti,0,sizeof(ti));
	priority_queue<point> q;
	q.push((point){s,0,0});
	while(q.size())
	{
		point p=q.top();q.pop();
		ti[p.v]++;
		if (ti[p.v]==k&&p.v==t) return p.g+p.h;
		for (int i=0;i<e[p.v].size();i++)
		{
			edge y=e[p.v][i];
			q.push((point){y.to,p.g+y.w,dis[y.to]});
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	int n,r,a,b,c;cin>>n>>r;
	for (int i=1;i<=r;i++)
	{
		cin>>a>>b>>c;
		addedge(a,b,c);
	}
	dijkstra(n);
	cout<<astar(1,n,2);
	return 0;
}