#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <list>
#include <deque>
#include <bitset>
#include <iterator>
#include <cctype>
#include <sstream>
#include <utility>
#include <iomanip>
#include <limits>
#include <ctime>
#include <cstdlib>

// #define x first
// #define y second

// typedef long long LL;
// typedef std::pair<int,int> PII;
// typedef std::vector<int> VEC;
// typedef std::queue<int> QUE;
// typedef std::stack<int> STK;
// typedef std::set<int> SET;
// typedef std::map<int,int> MAP;
// typedef std::bitset<L> BS;

// const int L=; // L!=1e9+10
const int inf=0x3f;
const int err=-1;
// const double eps=1e-8;
// const double pi=acos(-1.0);
const int N=5e2+10;
const int M=1e5+10;
// int dx[]={ 0 , 0 , 1 , -1 };
// int dy[]={ 1 , -1, 0 , 0  };
// LL mod=1e9+7;

using namespace std;

inline int read()
{
	int f=1;
	int x=0;
	char c=getchar();

	while(c<'0'||c>'9')
	{
		if(c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	
	while('0'<=c&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}

	return f*x;
}

void write(int x)
{
    if(x<0)
	{
        putchar('-'),x=-x;
	}
    if(x>9)
	{
        write(x/10);
	}
    putchar(x%10+'0');
	
    return;
}

int n,m;// n=V.size(); m=E.size()
int g[N][N];// graph

int dist[N];// 1->others
int s[N];// points found

inline void init_a()
{
	// initialize graph
	memset(g,inf,sizeof(g));// all set inf
	for(int i=1,j=1;i<=n&&j<=n;i++,j++)
	{
		g[i][j]=0;// set 0 diagonally (i==j)
	}
	
	// initialize s
	for(int i=1;i<=n;i++)
	{
		s[i]=0;
	}
	s[1]=1;

	return;
}

inline void init_b()
{
	// initialize dist
	for(int i=1;i<=n;i++)
	{
		dist[i]=g[1][i];
	}

	return;
}

int Dijkstra()
{
	// Dijkstra
	int node=-1;
	for(int i=1;i<n-1;i++)
	{
		int minx=inf;
		for(int j=1;j<=n;j++)
		{
			if(s[j]==0&&(node==-1||dist[j]<minx))
			{
				minx=dist[j];
				node=j;
			}
		}

		s[node]=1;
		for(int k=1;k<=n;k++)
		{
			if(g[node][k]<inf)
			{
				if(dist[k]>dist[node]+g[node][k])
				{
					dist[k]=dist[node]+g[node][k];
				}
			}
		}
	}

	if(dist[n]==inf)
	{
		return -1;
	}
	else
	{
		return dist[n];
	}
}

int main()
{
	#ifndef ONLINE_JUDGE
		freopen(".in","r",stdin);
		freopen(".out","w",stdout);
	#endif

	init_a();

	// read n&m
	n=read();
	m=read();

	// read edges
	for(int i=0;i<m;i++)
	{
		int x,y,z;// x--z->y
		x=read();
		y=read();
		z=read();
		g[x][y]=min(g[x][y],z);
	}

	init_b();
	
	// write (dist_1->n)_min
	write(Dijkstra());
	puts("");

	return 0;
}