#include<cstdio>
using namespace std;

const int N=30000+1,M=150000+1,INF=99999999;

int arcNum=0,heap_size;

int heap[N],h[N];

struct arc{
	int go;
	int next;
	int data;
	arc(){
		go=next=-1;
		data=INF;
	}
} arcArray[M];

int first[N]={0},dis[N];

void addarc(int,int,int);
int get();
void climb(int);

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		dis[i]=INF,heap[i]=h[i]=i;
	heap_size=n;
	int x,y,z;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		addarc(x,y,z);
	}
	dis[1]=0;
	for(int i=1;i<n;i++)
	{
		int r;
		int temp,mi=INF;
		r=get();
		for(int j=first[r];arcArray[j].next!=-1;j=arcArray[j].next)
		{
			if(dis[arcArray[j].go]>dis[r]+arcArray[j].data)
			{
				dis[arcArray[j].go]=dis[r]+arcArray[j].data;
				climb(h[arcArray[j].go]);
			}
		}
	}
	printf("%d\n",dis[n]);
	return 0; 
}

void addarc(int a,int b,int c)
{
	arcNum++;
	arcArray[arcNum].data=c;
	arcArray[arcNum].go=b;
	arcArray[arcNum].next=first[a];
	first[a]=arcNum;
} 

int get()
{
	int now=1,next,res,temp;
	res=heap[1];
	heap[1]=heap[heap_size--];
	h[heap[1]]=1;
	while(now*2<=heap_size)
	{
		next=now*2;
		if(next<heap_size&&dis[heap[next]]>dis[heap[next+1]]) next++;
		if(dis[heap[now]]<=dis[heap[next]]) break;
		temp=heap[now];
		heap[now]=heap[next];
		heap[next]=temp;
		h[heap[now]]=now;
		h[heap[next]]=next;
		now=next;
	}
	return res;
}

void climb(int node)
{
	if(node==1) return;
	if(dis[heap[node]]>=dis[heap[node/2]]) return;
	int temp;
	temp=heap[node];
	heap[node]=heap[node/2];
	heap[node/2]=temp;
	h[heap[node]]=node;
	h[heap[node/2]]=node/2;
	climb(node/2);
	return;
}