#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define M 50005
#define N 255
int n,m,e,ans,edge,del,size;
int head[M],w[M],next[M];
int order[M];
int p[N],d[N],pre[N],pos[N];
int heap[1010];
bool v[N];
void add(int x,int y,int c){
	head[++e]=y;w[e]=c;
	next[e]=p[x];
	p[x]=e;
}
void up(int x){
	int y;
	while(x>1){
		y=x>>1;
		if (d[heap[x]]<d[heap[y]]){
			swap(pos[heap[x]],pos[heap[y]]);
			swap(heap[x],heap[y]);
			x=y;
			y=x>>1;
		}
		else break;
	}
}
void down(int x,int n){
	int y=x<<1;
	while(x<=n){
		if (y<n && d[heap[y]]>d[heap[y+1]]) y++;
		if (d[heap[x]]>d[heap[y]]){
			swap(pos[heap[x]],pos[heap[y]]);
			swap(heap[x],heap[y]);
			x=y;
			y=x<<1;
		}
		else break;
	}
}
void heap_dj(){
	memset(d,0x3f3f3f3f,sizeof(d));
	memset(v,0,sizeof(v));
	memset(pos,0,sizeof(pos));
	d[1]=0;
	heap[size=1]=1;
	v[1]=true;
	pos[1]=1;
	int x,j,y;
	while(size){
		x=heap[1];
		for(j=p[x];j;j=next[j])
		if(d[y=head[j]]>d[x]+w[j])
		{
		   d[y]=d[x]+w[j];
		   pre[y]=j;
		   up(pos[y]);
		   if (!v[y]){
		   	  v[y]=true;
		   	  heap[++size]=y;
		   	  pos[y]=size;
		   	  up(size);
		   }
		}
		pos[heap[size]]=1;
		heap[1]=heap[size];
		size--;
		down(1,size);
	}
}
int main(){
	freopen("rblock.in","r",stdin);
	freopen("rblock.out","w",stdout);
	int x,y,c;
	cin>>n>>m;
	e=1;
	memset(p,0,sizeof(p));
	while(m--){
		scanf("%d%d%d",&x,&y,&c);
		add(x,y,c);
		add(y,x,c);
	}
	heap_dj();
	ans=d[n];
	edge=0;
	for(int j=pre[n];j;j=pre[head[j^1]])
	if (edge<w[j]) {
	    edge=w[j];
	    order[0]=0;
	    order[++order[0]]=j;
    }
    else if (edge==w[j]){
    	order[++order[0]]=j;
    }
    del=0;
    for(int i=1;i<=order[0];++i){
    	w[order[i]]*=2;
	    w[order[i]^1]*=2;
	    heap_dj();
	    if(del<d[n]) del=d[n];
	    w[order[i]]/=2;
	    w[order[i]^1]/=2;
    }
	printf("%d\n",del-ans);
	return 0;
}