#include<bits/stdc++.h>
#define N 5010
#define M 200010
#define V 
#define INF 0x7fffffff
#define _INF 1e18
#define oo 0x3f3f3f3f
#define inf 0x3fffffff
#define int LL
#define LD long double
#define LL long long
#define LLU unsigned long long
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define _FOR(i,l,r,x) for(int i=(l);i<=(r);i+=x)
#define REP(i,l,r) for(int i=(l);i>=(r);--i)
#define _REP(i,l,r,x) for(int i=(l);i>=(r);i-=x)
#define LIN(p,l) for(int p=(l);p;p=nxt[p])
#define fin(x) freopen(x".in","r",stdin);
#define fout(x) freopen(x".out","w",stdout);
using namespace std;
inline int read()
{
	char ch;int f=1,x;
	while(ch=getchar(),!isdigit(ch)) if(ch=='-') f=-1;x=(ch^48);
	while(ch=getchar(),isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
inline void write(int x)
{
	if(x<0)
	{
		putchar('-');
		write(-x);
		return;
	}
	if(x>=10) write(x/10);
	putchar(x%10^48);
}
inline void writ(int x)
{
	write(x);
	puts("");
}
int h[N],nxt[M],ver[M],edge[M],tot;
int n,m,dis[N],dis2[N];
struct nod{
	int x,dis;
	nod(){};
	nod(int a,int b)
	{
		x=a,b=dis;
	}
};
bool operator < (const nod& a,const nod&b)
{
	return a.dis>b.dis;
}
void add(int x,int y,int z)
{
	++tot;
	ver[tot]=y,edge[tot]=z,nxt[tot]=h[x],h[x]=tot;
}
void dijkstra()
{
	priority_queue<nod> q;
	memset(dis,0x3f,sizeof(dis));
	memset(dis2,0x3f,sizeof(dis2));
	q.push(nod(1,0));
	dis[1]=0;
	while(q.size())
	{
		int u=q.top().x;q.pop();
		LIN(i,h[u])
		{
			if(dis[u]+edge[i]<dis[ver[i]])
			{
				dis2[ver[i]]=dis[ver[i]];
				dis[ver[i]]=dis[u]+edge[i];
				q.push(nod(ver[i],dis[ver[i]]));
			}
			else if(dis[u]+edge[i]<dis2[ver[i]])
				dis2[ver[i]]=dis[u]+edge[i];
		}
	}
}
signed main()
{
	n=read(),m=read();
	FOR(i,1,m)
	{
		int x=read(),y=read(),z=read();
		add(x,y,z);
		add(y,x,z);
	}
	dijkstra();
	writ(dis2[n]);
	return 0;
}

快疯了