#include<iostream>
#include<cstdio>
#include<memory.h>
#include<vector>
#include<queue>

using namespace std;

#define Clear(f) memset(f, 0, sizeof(f))

const int SIZE = 30005;
const int INF = 1 << 30;

int d[SIZE];
struct cmp
{
	bool operator()(const int a, const int b)const
	{
		return d[a] > d[b];
	}
};
struct Edge{int v, w;};
vector<Edge> path[SIZE];

int Dij(int st, int et)
{
	bool vis[SIZE];
	priority_queue<int, vector<int>, cmp> q;
	for(int i = st; i <= et; i ++) {
		d[i] = INF;
		vis[i] = 0;
	}

	d[st] = 0;
	q.push(st);
	while(!q.empty()) {
		int tmp = q.top();
		q.pop();
		if(tmp == et) return d[et];
		if(vis[tmp]) continue;
		vis[tmp] = 1;
		
		for(int i = 0; i < path[tmp].size(); i ++) {
			int v = path[tmp][i].v;
			int w = path[tmp][i].w;
			if(!vis[v] && d[v] > d[tmp] + w) {
				d[v] = d[tmp] + w;
				q.push(v);
			}
		}
	}
	//return d[et];
}

int main()
{
	int n, m;
	int a, b, len;
	while(scanf("%d%d", &n, &m) != EOF) {
		for(int i = 1; i <= n; i ++)
			path[i].clear();
		for(int i = 0; i < m; i ++) {
			scanf("%d%d%d", &a, &b, &len);
			Edge p;
			p.v = b, p.w = len;
			path[a].push_back(p);
		}
		int ans = Dij(1, n);
		printf("%d\n", ans);
	}
}