#include<bits/stdc++.h>
using namespace std;

#define int long long

#define INF (int)1e16

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	vector<vector<pair<int,int>>>g(N);
	vector<tuple<int,int,int>>e;
	for(int i=0;i<M;i++){
		int a,b,c;
		cin>>a>>b>>c;
		g[a].emplace_back(b,c);
		g[b].emplace_back(a,c);
		e.emplace_back(a,b,c);
		e.emplace_back(b,a,c);
	}
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
	vector<int>d0(N,INF),d1(N,INF),p(N,-1),v(N);
	d0[0]=0;
	q.emplace(0,0);
	while(!q.empty()){
		auto[d,i]=q.top();
		q.pop();
		if(d0[i]<d){
			continue;
		}
		for(auto[j,w]:g[i]){
			if(d0[i]+w<d0[j]){
				d0[j]=d0[i]+w;
				p[j]=i;
				q.emplace(d0[j],j);
			}
		}
	}
	for(int i=N-1;i>=0;i=p[i]){
		v[i]=1;
	}
	d1[N-1]=0;
	q.emplace(0,N-1);
	while(!q.empty()){
		auto[d,i]=q.top();
		q.pop();
		if(d1[i]<d){
			continue;
		}
		for(auto[j,w]:g[i]){
			if(d1[i]+w<d1[j]){
				d1[j]=d1[i]+w;
				q.emplace(d1[j],j);
			}
		}
	}
	int ans=INF-1;
	for(auto[a,b,c]:e){
		if(v[a]&&v[b]){
			continue;
		}
		int x=d0[N-1]-d0[a]-d1[b];
		if(x<=0){
			continue;
		}
		ans=min(ans,c-x+1);
	}
	cout<<(ans+1)%INF-1<<'\n';
	return 0;
}