#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int n, m;
    cin >> n >> m;
    vector<array<ll, 3>> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
        edges[i][0]--, edges[i][1]--;
    }
    vector<ll> cost(n, 1e18);
    cost[0] = 0;
    for (auto [a, b, w] : edges) {
        for (int i = 0; i < n; i++) {
            cost[b] = min(cost[b], max<ll>(0, cost[a] + w));
        }
    }
    vector<ll> newcost = cost;
    for (auto [a, b, w] : edges) {
        if (cost[a] + w < cost[b]) {
            newcost[b] = 0;
        }
    }
    for (auto [a, b, w] : edges) {
        for (int i = 0; i < n; i++) {
            newcost[b] = min(newcost[b], max<ll>(0, newcost[a] + w));
        }
    }
    cout << newcost[n - 1] << '\n';
}