#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define For(i, x, y) for (ll i = x; i <= y; ++ i)
#define Dor(i, x, y) for (ll i = x; i >= y; -- i)
#define ll long long
using namespace std;
ll n, e, a[210][210], x, y, z, f[210];
int main() {
	cin >> n >> e;
	For (i, 1, n) {
		cin >> x >> y >> z;
		a[x][y] = z;
	}
	For (i, 1, n) f[i] = INT_MAX;
	f[n] = 0;
	Dor (i, n - 1, 1)
		For (j, i + 1, n)
			if (a[i][j] > 0 && f[j] != INT_MAX && f[i] > a[i][j] + f[j])
				f[i] = min(f[i], a[i][j] + f[j]);
	cout << f[1];
	return 0;
}