#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define len 30005
#define inf 1000000007
using namespace std;
int d[len],head[len],k,m,n;
bool vis[len];
struct node
{
	int j,v,next;
}s[5*len];
void add(int x,int y,int z)
{
	s[k].j=y;
	s[k].v=z;
	s[k].next=head[x];
	head[x]=k++;
}
struct comp
{
	bool operator()(int a,int b)
{
	return d[a]>d[b];
}
};
void dijstra(int x)
{
	d[x]=0;
	priority_queue<int,vector<int>,comp> q;
	q.push(x);
	while(!q.empty())
	{
		int temp=q.top();
		q.pop();
		vis[temp];
		for(int i=head[temp];i!=-1;i=s[i].next)
		{
			int j=s[i].j;
			if(!vis[j]&&d[j]>d[temp]+s[i].v)
			{
				d[j]=d[temp]+s[i].v;
				q.push(j);
			}
		}
	}
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		int x,y,z,start;
		k=0;
		start=inf;
		memset(head,-1,sizeof(head));
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
			start=min(start,x);
		}
		for(int i=1;i<=n;i++) vis[i]=0,d[i]=inf;
		dijstra(start);
		printf("%d\n",d[n]);    
	}
	return 0;
}