#include<bits/stdc++.h>
#define N 100005
#define f first
#define s second
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const long long INF = 1000000000000000000ll;

vector<pii> graf[N], GT[N];//para {u,nr}
pii kr[2*N];
ll odlStart[N], odlKoniec[N];
int path[N];//poprzednik wierzcholka [v] na drodze 1 -> n
int isOnPath[2*N];//czy ita krawedz jest na sciezce 1 -> n

int n, m, waga[2*N];//waga itej krawedzi
priority_queue<pair<long long, int>> Q;


void wczytaj() {
	cin>>n>>m;
	for(int i= 1; i <= m; i++) {
		int v, u, c;
		cin>>v>>u>>c;
		graf[v].pb({u,i});
		GT[u].pb({v,i});
		waga[i] = c;
		kr[i] = {v,u};
	}
}

void dijkstra1() {
	for(int i = 1; i <= n; i++)
		odlStart[i] = INF;
	odlStart[1] = 0;
	Q.push({0,1});
	while(Q.size()) {
		int v = Q.top().second;
		ll dist = Q.top().first * (-1);
		Q.pop();
		if(dist > odlStart[v])
			continue;
		for(auto it: graf[v]) {
			int u = it.f, kraw = waga[it.s];
			if(dist + kraw < odlStart[u]) {
				odlStart[u] = dist + kraw;
				path[u] = v;
				Q.push({-odlStart[u],u});
			}
		}
	}
//	for(int i = 1; i <= n; i++)
//		cout<<"v="<<i<<" odl="<<odlStart[i]<<" path="<<path[i]<<"\n";
}

void dijkstra2() {
	for(int i = 1; i <= n; i++)
		odlKoniec[i] = INF;
	odlKoniec[n] = 0;
	Q.push({0,n});
	while(Q.size()) {
		int v = Q.top().second;
		ll dist = Q.top().first * (-1);
		Q.pop();
		if(dist > odlKoniec[v])
			continue;
		for(auto it: GT[v]) {
			int u = it.f, kraw = waga[it.s];
			if(dist + kraw < odlKoniec[u]) {
				odlKoniec[u] = dist + kraw;
				Q.push({-odlKoniec[u],u});
			}
		}
	}
//	for(int i = 1; i <= n; i++)
//		cout<<"v="<<i<<" odlKoniec="<<odlKoniec[i]<<"\n";
}

void sciezka() {
	int v = n;
	while(v != 1) {
		int u = path[v];
		for(auto it: graf[u])
			if(it.f == v)
				isOnPath[it.s] = 1;
		v = u;
	}
//	for(int i = 1; i <= m; i++)
//		cout<<"i="<<i<<" isOnPath="<<isOnPath[i]<<"\n";
}

void findAns() {
	ll ans = INF;
	for(int i = 1; i <= m; i++)
		if(isOnPath[i] == 0) {
			int v = kr[i].f, u = kr[i].s;
			if(odlStart[v] + odlKoniec[u] + waga[i] < ans)
				ans = odlStart[v] + odlKoniec[u] + waga[i];
		}
	if(ans == INF)
		cout<<"-1";
	else
		cout<<ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	wczytaj();
	dijkstra1();
	dijkstra2();
	sciezka();
	findAns();
	return 0;
}