#include <iostream>
#include <algorithm>
#include <list>
using namespace std;
struct node
{
    int v,weight;
};
#define INT_MAX 10000000
#define  N  30005
list < node > adj[N];//邻接表，点从1开始计数
list < node > :: iterator ite;
int heap[N],heapindex[N],visited[N],dis[N];
void makeheap1(int change)//最小堆，change处变小，向上调整
{
	int parent;
	while(change!=1)
	{
		parent=change/2;
		if(dis[heap[parent]]>dis[heap[change]])
		{
			//	swap(heapindex[heap[parent]],heapindex[heap[change]]);
			swap(heap[parent],heap[change]);
			heapindex[heap[parent]]=parent;
			heapindex[heap[change]]=change;
			change=parent;
		}
		else break;
	}
}
void makeheap2(int n)//1--n的最小堆，堆顶元素的调整
{
	int parent,lson,rson,pw,lw,rw;
	parent=1;
	lson=parent*2;
	rson=parent*2+1;
	while(lson>n)//没有孩子了
	{
		pw=dis[heap[parent]];
		lw=dis[heap[lson]];
		rw=dis[heap[rson]];
		if(rson>n)rw=INT_MAX;
		if(pw<=lw&&pw<=rw)return;
		if(lw<rw)
		{//左交换
			//	swap(heapindex[heap[parent]],heapindex[heap[lson]]);
			swap(heap[parent],heap[lson]);
			heapindex[heap[parent]]=parent;
			heapindex[heap[lson]]=lson;
			parent=lson;
		}
		else 
		{
			//	swap(heapindex[heap[parent]],heapindex[heap[rson]]);
			swap(heap[parent],heap[rson]);
			heapindex[heap[parent]]=parent;
			heapindex[heap[rson]]=rson;
			parent=rson;
		}
		lson=parent*2;
		rson=parent*2+1;
	}
	
}
void dijkstra(int s,int n)
{
    int i,pose,v,w;
	for(i=1;i<=n;++i){heap[i]=i;heapindex[i]=i;}
	fill(dis,dis+n+1,INT_MAX);
	memset(visited,0,sizeof(visited));
	dis[s]=0;
	makeheap1(heapindex[s]);
    for(i=1;i<=n;++i)
    {
		pose=heap[1];
		if(dis[pose]==INT_MAX)return;
		if(pose==n)return;
        visited[pose]=true;
		heap[1]=heap[n-i+1];//在还有n-i+1个元素的堆中删除第一个元素
		heapindex[heap[1]]=1;
		makeheap2(n-i);//调整还有n-i个元素堆
        for(ite=adj[pose].begin();ite!=adj[pose].end();++ite)
        {
			v=ite->v;
			w=ite->weight;
			if(!visited[v]&&dis[pose]+w<dis[v])
			{
				dis[v]=dis[pose]+w;
				makeheap1(heapindex[v]);
			}
        }
    }
}
int main()
{
    int s,t,w,n,m;
    node temp;
    cin>>n>>m;
    while(m--)
    {
        scanf("%d%d%d",&s,&t,&w);
        temp.v=t;
        temp.weight=w;
        adj[s].push_back(temp);
    }
	dijkstra(1,n);
    cout<<dis[n]<<endl;
    return 0;
}