#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define _ 0
#define I using
#define AK namespace
#define IOI std
#define int long long
#define pii pair <int,int>
#define fx first
#define fy second
I AK IOI;
const int N = 1e4 + 10;
int n,m,u[N],v[N],w[N],ans,d[N];
int h[N],ver[N],e[N],ne[N],idx;
bool st[N];
void add(int u,int v,int w){
	idx++,ver[idx] = v,e[idx] = w,ne[idx] = h[u],h[u] = idx;
}
int dij(int s,int t){
	priority_queue <pii,vector<pii>,greater<pii> > heap;
	heap.push({0,s});
	memset(d,0x3f,sizeof(d));
	d[s] = 0;
	memset(st,false,sizeof(st));
	while(heap.size()){
		pii T = heap.top();
		heap.pop();
		int x = T.fy;
		if(st[x]){
			continue;
		}
		st[x] = true;
		for(int i = h[x];i != -1;i = ne[i]){
			int j = ver[i];
			if(x + e[i] < d[j]){
				d[j] = x + e[i];
				heap.push({d[j],j});
			}
		}
	}
	return d[t];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		cin >> u[i] >> v[i] >> w[i];
	}
	for(int k = 1;k <= m;k++){
		memset(h,-1,sizeof(h));
		idx = 0;
		for(int i = 1;i <= m;i++){
			if(i == k){
				add(u[i],v[i],w[i] * 2),add(v[i],u[i],w[i] * 2);
			} else {
				add(u[i],v[i],w[i]),add(v[i],u[i],w[i]);
			}
		}
		int h = dij(1,n);
		ans = max(ans,h);
	}
	memset(h,-1,sizeof(h));
	idx = 0;
	for(int i = 1;i <= m;i++){
		add(u[i],v[i],w[i]),add(v[i],u[i],w[i]);
	}
	cout << ans - dij(1,n);
	return ~~(0^_^0);
}