#include"iostream"
#include"cstdio"
#include"cstring"
#include"algorithm"
#include"cstdlib"
#include"queue"
#include"vector"
using namespace std;
const int inf=0x7fffffff;
const int ms=100001;
struct edge
{
	//int from;
	int to;
	int cost;
};
typedef pair<int,int> P;
int main()
{
	int i,j,N,R,ans,a,b,w;
	scanf("%d%d",&N,&R);
	vector<edge> vec[N+1]; 
	for(i=1;i<=R;i++)
	{
		scanf("%d%d%d",&a,&b,&w);
		edge e;
		e.to=b;
		e.cost=w;
		//vec[a].push_back(edge{b,w});  有警告 
		vec[a].push_back(e);
		e.to=a;
		vec[b].push_back(e);
	}
	int dist[N+1],dist2[N+1];
	priority_queue<P,vector<P>,greater<P> > que;
	fill(dist,dist+N+1,inf);
	fill(dist2,dist2+N+1,inf);
	dist[1]=0;
	que.push(P(0,1));
	while(!que.empty())
	{
		P p=que.top();
		que.pop();
		int v=p.second;
		int d=p.first;
		if(dist2[v]<d)
			continue;
		for(i=0;i<vec[v].size();i++)
		{
			edge &e=vec[v][i];
			int d2=d+e.cost;
			if(dist[e.to]>d2)
			{
				swap(dist[e.to],d2);
				que.push(P(dist[e.to],e.to));
			}
			if(dist2[e.to]>d2&&dist[e.to]<d2)
			{
				dist2[e.to]=d2;
				que.push(P(dist2[e.to],e.to));
			}
		}
	}
	//printf("%d\n",dist2[N]);
	cout<<dist2[N]<<endl;
	return 0;
}