#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<climits>
using namespace std;
typedef pair<int,int> P;
int n,m;
struct edge{
	int to,cost;
	edge(int to,int cost){
		this->to=to;
		this->cost=cost;
	}
	edge() {}
};
int head[30010],next[160000],cnt;
edge G[160000];
int dist[30010];
priority_queue <P, vector<P>, greater<P> > que;

void Dijkstra(){
	fill(dist+1,dist+1+n,INT_MAX);
	dist[1]=0;
	que.push(make_pair(dist[1],1));
	while(!que.empty()){
		P p=que.top();
		que.pop();
		if(p.first>dist[p.second]) continue;
		else{
			int u=p.second;
			for(int i=head[u];i!=-1;i=next[i]){
				int v=G[i].to;
				if(dist[v]>dist[u]+G[i].cost){
					dist[v]=dist[u]+G[i].cost;
					que.push(make_pair(dist[v],v));
				}
			}
		}
	}
}


void init(){
	while(!que.empty()) que.pop();
	memset(head,-1,sizeof(head));
	cnt=0;
}


void add(int from,int to,int cost){
	next[cnt]=head[from];
	G[cnt]=edge(to,cost);
	head[from]=cnt;
	cnt++;
}


int main(){
	#ifdef ONLINE_JUDGE
	#else
		freopen("in.txt","r",stdin);
	#endif
	while(scanf("%d %d",&n,&m)!=EOF){
		init();
		for(int i=0;i<m;i++){
			int u,v,w;
			scanf("%d %d %d",&u,&v,&w);
			add(u,v,w);
		}	
		Dijkstra();
		printf("%d\n",dist[n]);
	}
         return 0;
}