/* 
 * Problem: pku3255 Roadblocks
 * Author: Guo Jiabao
 * Time: 2009.4.14 10:32
 * State: Solved
 * Memo: 次短路径 Dijkstra + Heap (特殊)
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=5001,MAXM=200001,INF=0x7FFFFFF;
using namespace std;
struct Minheap
{
	struct HeapElement
	{
		int key,value;
	}H[MAXN];
	int size,Position[MAXN];
	void init(){H[size=0].value=-INF;}
	void shift(int key,int value,int pos)
	{
		int i,f;
		HeapElement p={key,value};
		for (i=pos;p.value < H[f=i>>1].value;i=f)
		{
			H[i]=H[f];
			Position[H[i].key]=i;
		}
		H[i]=p;
		Position[H[i].key]=i;
	}
	void ins(int key,int value){shift(key,value,++size);}
	void decrease(int key,int value){shift(key,value,Position[key]);}
	void delmin()
	{
		int i,c;
		HeapElement p=H[size--];
		for (i=1;(c=i<<1)<=size;i=c)
		{
			if (c+1 <=size && H[c+1].value < H[c].value)
				c++;
			if (H[c].value < p.value)
			{
				H[i]=H[c];
				Position[H[i].key]=i;
			}
			else
				break;
		}
		H[i]=p;
		Position[H[i].key]=i;
	}
}H;
struct edge
{
	edge *next;
	int t,c;
}ES[MAXM],*V[MAXN];
int N,M,EC=-1,Shortest,Ans;
int sp[2][MAXN];
inline void addedge(int a,int b,int c)
{
	ES[++EC].next=V[a];
	V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
	ES[++EC].next=V[b];
	V[b]=ES+EC; V[b]->t=a; V[b]->c=c;
}
void init()
{
	int i,a,b,c;
	freopen("block.in","r",stdin);
	freopen("block.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
	}
}
void dijkstra(int S,int *sp)
{
	int i,j;
	H.init();
	for (i=1;i<=N;i++)
		H.ins(i,sp[i]=INF);
	H.decrease(S,sp[S]=0);
	for (i=S;;)
	{
		H.delmin();
		for (edge *e=V[i];e;e=e->next)
		{
			j=e->t;
			if (sp[i] + e->c <sp[j])
				H.decrease(j,sp[j]=sp[i] + e->c);
		}
		if (H.size)
			i=H.H[1].key;
		else
			break;
	}
}
void solve()
{
	int i,c;
	dijkstra(1,sp[0]);
	dijkstra(N,sp[1]);
	Shortest=sp[0][N];
	Ans=INF;
	for (i=0;i<=EC;i+=2)
	{
		edge *e1=ES+i,*e2=ES+i+1;
		int a=e1->t,b=e2->t;
		c=sp[0][a] + sp[1][b] + e1->c;
		if (c < Ans && c>Shortest)
			Ans=c;
		c=sp[1][a] + sp[0][b] + e1->c;
		if (c < Ans && c>Shortest)
			Ans=c;
	}
}
int main()
{
	init();
	solve();
	printf("%dn",Ans);
	return 0;
}