CSES - Shared codeLink to this code: https://cses.fi/paste/44db546d30a77b7863a4ba/
#include<bits/stdc++.h>
using namespace std;
#define nline '\n';
#define fastio            ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;cout<<setprecision(15);
typedef  long long   ll;
typedef  long double ld;
const ll   N     =  2505;
const ll   mod   =  1e9 + 7;
// const ll mod = 998244353;
const ll   inf   =  1e16;
int dx[] = { -1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};


vector<pair<ll, ll>>g[N];
int n;
bool reachable(int node) {
    queue<int>q;
    q.push(node);
    vector<int>vis(N);
    vis[node] = 1;
    while (q.size()) {
        int par = q.front();
        q.pop();
        for (auto p : g[par]) {
            int child = p.first;
            if (!vis[child]) {
                vis[child] = 1;
                q.push(child);
            }
        }
    }
    return vis[n];
}

void solve() {
    int  m;
    cin >> n >> m;
    vector<vector<ll>>edges;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        edges.push_back({u, v, w});
    }

    vector<ll>dist(n + 1, -inf);
    dist[1] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (auto &v : edges) {
            ll from = v[0], to = v[1], w = v[2];
            if (dist[from] != -inf and dist[from] + w > dist[to]) dist[to] = dist[from] + w;
        }
    }
    for (int i = 0; i < m; i++) {
        ll u = edges[i][0], v = edges[i][1], w = edges[i][2];
        if (dist[u] != -inf and dist[u] + w > dist[v] and reachable(v)) {
            cout << -1;
            return;
        }
    }
    cout << dist[n];

}


int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fastio;
    int tc = 1;
    // cin >> tc;
    int t = tc;
    while (tc--) {
        //cout << "Case #" << t - tc << ": ";
        solve();
        cout << nline;
    }
    return 0;
}