#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
using namespace std;
const int M=30010;
struct graph
{
	int d;
	int v;
}g[M][30];
int len[M];
char used[M];
int dist[M];
struct graph newg;

struct cmp
{
	bool operator()(const struct graph &a,const struct graph &b)
	{
	     return a.d>b.d;
	}
};
int n,m;
int dijkstra()
{
	int i,j;
	int u,v;
	memset(used,0,sizeof(used));
	priority_queue<graph,vector<graph>,cmp>pq;
	for(i=1;i<=n;i++)
		dist[i]=INT_MAX;
	dist[1]=0;
	for(i=1;i<=len[1];i++)
	{
		pq.push(g[1][i]);
		dist[g[1][i].v]=g[1][i].d;
	}
	used[1]=1;
	for(i=1;i<=n;i++)
	{
		newg=pq.top();
		pq.pop();
		if(newg.v==n)return dist[newg.v];
		v=newg.v;
		used[v]=1;
		for(j=1;j<=len[v];j++)
			if((!used[g[v][j].v]))
			{
				int newdist=dist[v]+g[v][j].d;
				if(newdist<dist[g[v][j].v])
				{
					dist[g[v][j].v]=newdist;
					newg.v=g[v][j].v;
					newg.d=newdist;
					pq.push(newg);
				}
			}	
	}
	
}
int main()
{
	int i;
	int a,b,c;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(len,0,sizeof(len));
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			len[a]++;
			if(len[a]>=30)while(1);
			g[a][len[a]].d=c;
			g[a][len[a]].v=b;
		}
		printf("%d\n",dijkstra());
	}
	return 0;
}