AC

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Edge {

int v;
int w;

};

int main() {

int n, m;
cin >> n >> m;
vector<vector<Edge>> adj(n + 1);
vector<int> in_degree(n + 1, 0);

for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    in_degree[v]++;
}

vector<int> topo_order;
queue<int> q;

for (int i = 1; i <= n; ++i) {
    if (in_degree[i] == 0) {
        q.push(i);
    }
}

while (!q.empty()) {
    int u = q.front();
    q.pop();
    topo_order.push_back(u);
    
    for (const Edge& e : adj[u]) {
        int v = e.v;
        in_degree[v]--;
        if (in_degree[v] == 0) {
            q.push(v);
        }
    }
}

vector<long long> dist(n + 1, LLONG_MIN);
dist[1] = 0;

for (int u : topo_order) {
    if (dist[u] != LLONG_MIN) {
        for (const Edge& e : adj[u]) {
            int v = e.v;
            int w = e.w;
            if (dist[v] < dist[u] + w) {
                dist[v] = dist[u] + w;
            }
        }
    }
}

if (dist[n] == LLONG_MIN) {
    cout << -1 << endl;
} else {
    cout << dist[n] << endl;
}

return 0;

}