#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
#define N 300
#define M 55001
struct arr{
	int tt,ww,next,ff;
}c[M];
int r[M];
bool v[M],f[M];
int dis[N];
int tot = 1;
struct heap{
	struct data{
		int ww,xx;
	}h[M];
	int sum;
	void clean(){
		memset(h,0,sizeof(h));
		sum = 0;
	}
	
	void up(int x){
		int p = x >> 1;
		while (p){
			if (h[p].ww > h[x].ww) swap(h[p],h[x]);
			else return;
			x = p;
			p = x >> 1;	
		}
		return;
	}
	
	void down(int x){
		int p = x << 1;
		while (p <= sum){
			if (p < sum && h[p].ww > h[p + 1].ww) p++;
			if (h[p].ww < h[x].ww) swap(h[p],h[x]);
			else return;
			x = p;
			p = x << 1;
		}
		return;
	}
	
	void push(int xx,int ww){
		h[++sum].xx = xx;
		h[sum].ww = ww;
		if (sum == 1) return;
		up(sum);
	}
	
	void pop(){
		h[1] = h[sum --];
		if (!sum) return;
		down(1);
	}
	
	inline int top(){
		return h[1].xx;
	}
	inline int size(){
		return sum;
	}
	
}Q;
int n,m;

int heap_dijsktra(){
	memset(dis,0x3f,sizeof(dis));
	memset(v,0,sizeof(v));
	Q.clean();
	dis[1] = 0;
	Q.push(1,0);
	while (Q.size()){
		int x = Q.top();
		Q.pop();
		if (v[x]) continue;
		v[x] = 1;
		for (int i = r[x]; i; i = c[i].next){
			int y = c[i].tt;
			if (dis[y] > dis[x] + c[i].ww){
				dis[y] = dis[x] + c[i].ww;
				Q.push(y,dis[y]);
			}
		}
	}
	return dis[n];
}

inline void add(int x,int y,int z){
	c[++tot].ff = x;
	c[tot].tt = y;
	c[tot].ww = z;
	c[tot].next = r[x];
	r[x] = tot;
	return;
}

int main(){
	freopen("rblock.in","r",stdin);
	freopen("rblock.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,w;
	for (int i = 1; i <= m; i++){
		scanf("%d%d%d",&x,&y,&w);
		add(x,y,w);
		add(y,x,w);
	}
	int ww = heap_dijsktra();
	int ans = -1;
	for (int i = 2; i <= tot; i++){
		if (!f[i]){
			f[i] = f[i ^ 1] = 1;
			c[i].ww <<= 1;
			c[i ^ 1].ww <<= 1;
			int k = heap_dijsktra();
			ans = max(ans,k);
			c[i].ww >>= 1;
			c[i ^ 1].ww >>= 1 ;
		}
	}
	printf("%d\n",ans - ww);
	return 0;
}