#include<stdio.h>
#include<string.h>
#define maxint 0x7fffffff
#define maxL 30001
int n,m;
struct node{
	int vex;
	int num;
	node* next;
};
node* side[maxL];//邻接表
struct dnode{
	int id;
	int d;
};
dnode dist[maxL];//堆
int map[maxL];//从顶点号id映射到该顶点在堆中的位置（下标）
int len;

void filterdown(dnode heap[],int start,int end)
{
	if(start>=end)
		return;
	int i=start,j=2*i+1;
	dnode temp=heap[i];
	while(j<=end){
		if(j<end && heap[j].d>heap[j+1].d)
			j++;
		if(temp.d<=heap[j].d)
			break;
		else{
			heap[i]=heap[j];
			map[heap[i].id]=i;
			i=j;
			j=2*i+1;
		}
	}
	heap[i]=temp;
	map[heap[i].id]=i;
}
void filterup(dnode heap[],int site)
{
	int j=site,i=(j-1)/2;
	dnode temp=heap[j];
	while(j>0){
		if(heap[i].d<=temp.d)
			break;
		else{
			heap[j]=heap[i];
			map[heap[j].id]=j;
			j=i;
			i=(i-1)/2;
		}
		heap[j]=temp;
		map[heap[j].id]=j;
	}
}
void initialize()
{
	int i;
	for(i=0;i<n;i++){
		dist[i].d=maxint;
		dist[i].id=i;
		map[i]=i;
	}
	dist[0].d=0;
	node* p;
	for(p=side[0];p!=NULL;p=p->next)
		dist[p->vex].d=p->num;
	for(i=n/2;i>=0;i--){
		filterdown(dist,i,n-1);
	}
}
int extract_min()
{
	int u=dist[0].id;
	if(len==1){
		    len--;
			return u;
	}
	dist[0]=dist[len-1];
	map[dist[0].id]=0;
	len--;
	filterdown(dist,0,len-1);
	return u;
}
int dijkstra()
{
	initialize();
	int s[maxL];
	memset(s,0,sizeof(s));
	s[0]=1;
	for(;len>0;){
		int u=extract_min();
		s[u]=1;
		node* p;
		for(p=side[u];p!=NULL;p=p->next)
			if(s[p->vex]==0)
				if(dist[map[p->vex]].d>dist[map[u]].d+p->num){
					dist[map[p->vex]].d=dist[map[u]].d+p->num;
					filterup(dist,map[p->vex]);
				}
	}
	return dist[map[n-1]].d;
}					

int main()
{
//	freopen("f.in","r",stdin);
	int i;
	int a,b,c;
	
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=0;i<n;i++)
		    side[i]=NULL;
		len=n;
		for(i=0;i<m;i++){
			scanf("%d%d%d",&a,&b,&c);
			a--,b--;
			node* p;
			p=new node;
			p->vex=b;
			p->num=c;
			p->next=side[a];
			side[a]=p;
		}
		printf("%d\n",dijkstra());
	}
	return 0;
}