dp，但是不拓扑
过了。

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

using namespace std;

int n, m;
long long d[1501][1501];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1;i < n;i++) {
        for(int j = i + 1;j <= n;j++) {
            d[i][j] = -5000000001;
        }
    }
    for(int i = 1;i <= m;i++) {
        long long u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        d[u][v] = max(d[u][v], w);
    }
    for(int i = 1;i < n;i++) {
        for(int j = i + 1;j <= n;j++) {
            if(d[1][i] > -5000000001 && d[i][j] > -5000000001) {
                d[1][j] = max(d[1][j], d[1][i] + d[i][j]);
            }
        }
    }
    if(d[1][n] == -5000000001) {
        d[1][n] = -1;
    }
    printf("%lld", d[1][n]);
    return 0;
}