#include <bits/stdc++.h>
//#define out_kong(x) cout << x << ' ';
//#define out_huan(x) cout << x << '\n';
using namespace std;
const int N = 20010;
int n, m, a, b, c;
vector<int> e[N];
vector<int> len[N];
int Map[N][N];
int dfn[N], low[N], tot;
int instk[N];
int scc[N], siz[N], cnt;
stack<int>st;
void tarjan(int x) {
	dfn[x] = low[x] = ++tot;
	st.push(x);
	instk[x] = 1;
	for (int y : e[x]) {
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
		} else if (instk[y])
			low[x] = min(low[x], dfn[y]);
	}
	if (dfn[x] == low[x]) {
		int y;
		++cnt;
		do {
			y = st.top();
			st.pop();
			instk[y] = 0;
			scc[y] = cnt;
			++siz[cnt];
		} while (y != x);
	}
}
long long dis[105], vis[105], num[105];
queue<int>q;
void SPFA(int x) {
	while (q.size()) q.pop();
	for (int i = 1; i <= cnt; i++) {
		dis[i] = INT_MAX;
	}
	dis[x] = 0;
	q.push(x);
	while (!q.empty()) {
		int temp = q.front();
		q.pop();
		for (int j = 1; j <= cnt; j++) {
			if (dis[j] > Map[temp][j] + dis[temp]) {
				dis[j] = dis[temp] + Map[temp][j];
				if (!vis[j]) {
					q.push(j);
					vis[j] = 1;
					num[j]++;
				}
			}
		}
		vis[temp] = 0;
	}
}
int main() {
	cin >> n >> m;
	while (m--)
		cin >> a >> b >> c, e[a].push_back(b), len[a].push_back(c);
	for (int i = 1; i <= n; i++)
		if (!dfn[i]) tarjan(i);
//	for (int i = 1; i <= n; i++) {
//		out_kong(scc[i]);
//	}
//	out_huan(' ');
	for (int i = 1; i <= cnt; i++) {
		for (int j = 1; j <= cnt; j++) {
			Map[i][j] = INT_MAX;
		}
	}
	for (int i = 1; i <= cnt; i++) Map[i][i] = 0;
	for (int i = 1; i <= n; i++) {
		for (unsigned int j = 0 ; j < e[i].size(); j++) {
			if (scc[i] == scc[e[i][j]])	Map[scc[i]][scc[e[i][j]]] = 0;
			else {
//				printf("Map[%d][%d] = min(%d, %d);\n",scc[i],scc[e[i][j]],Map[i][scc[e[i][j]]],len[i][j]);
				Map[scc[i]][scc[e[i][j]]] = min(Map[i][scc[e[i][j]]], len[i][j]);
			}
		}
	}
	SPFA(scc[1]);
//	cout << "从" << scc[1] << "到" << scc[n] << endl;
//	for (int i = 1; i <= cnt; i++) {
//		for (int j = 1; j <= cnt; j++) {
//			cout << Map[i][j] << ' ';
//		}
//		cout << endl;
//	}
	cout << dis[scc[n]];
	return 0;
}