#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<bool> flood(n, false);
    flood[0] = true;
    for (int i = 0; i < n; i++) {
        for (auto [a, b, w] : edges) {
            if (flood[a]) flood[b] = true;
        }
    }


    vector<ll> cost(n, 1e18);
    vector<ll> costRed(n, 1e18);
    for (int i = 0; i < n; i++) {
        if (flood[i]) costRed[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        vector<ll> newCost(n, 1e18);
        newCost[0] = 0;
        for (auto [a, b, w] : edges) {
            cost[b] = min(cost[b], max<ll>(0, cost[a] + w));
            newCost[b] = min(newCost[b], max<ll>(0, costRed[a] + w));
        }
        swap(costRed, newCost);
    }
    for (auto [a, b, w] : edges) {
        if (max<ll>(0, cost[a] + w) < cost[b]) {
            cost[b] = min(cost[b], costRed[b]);
        }
    }
    cost[0] = 0;
    for (int i = 0; i < n; i++) {
        for (auto [a, b, w] : edges) {
            cost[b] = min(cost[b], max<ll>(0, cost[a] + w));
        }
    }
    cout << cost[n - 1] << '\n';
}

/*

3 3
1 2 1000
2 3 1
3 2 1



*/