// Source: https://usaco.guide/general/io

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

int main() {
	int n,m;cin>>n>>m;
	vector<vector<pair<int,int>>> v(n);
	for(int i = 0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	vector<int> disS(n,INT_MAX),disE(n,INT_MAX);
	priority_queue<pair<int, int>> q;
	disS[0]=0;
	disE[n-1]=0;
	q.push({0,0});
	vector<bool> proc1(n),proc2(n);
	while(!q.empty()){
		int a=q.top().second;
		q.pop();
		if(proc1[a])continue;
		proc1[a]=true;
		for(auto u:v[a]){
			int b=u.first,w=u.second;
			if(disS[b]>disS[a]+w){
				disS[b]=disS[a]+w;
				q.push({-disS[b],b});
			}
		}
	}
	q.push({0,n-1});
	while(!q.empty()){
		int a=q.top().second;
		q.pop();
		if(proc2[a])continue;
		proc1[a]=true;
		for(auto u:v[a]){
			int b=u.first,w=u.second;
			if(disE[b]>disE[a]+w){
				disE[b]=disE[a]+w;
				q.push({-disE[b],b});
			}
		}
	}
	int ans=INT_MAX;
	for(int i = 0;i<n;i++){
		for(auto u : v[i]){
			int a=i,b=u.first,c=u.second;
			if(disS[a]+disE[b]+c>disS[n-1]){
				if(disS[a]+disE[b]+c-disS[n-1]+1<c){cout<<a<<' '<<b<<endl;
					ans=min(ans,disS[a]+disE[b]+c-disS[n-1]+1);
				}
			}
			if(disS[b]+disE[a]+c>disS[n-1]){
				if(disS[a]+disE[b]+c-disS[n-1]+1<c){cout<<a<<' '<<b<<endl;
					ans=min(ans,disS[b]+disE[a]+c-disS[n-1]+1);
				}
			}
		}
	}cout<<(ans==INT_MAX?-1:ans)<<endl;
}