关键点：1. 可能1无法到点n 2.DAG图,可以用记忆化搜索
3.含有负权边 dfs的时候要注意INF的初值选取
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1510, M = 5e4 + 10;
ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
int h[N], idx;
struct ed{
    int to, from, w;
    int ne;
}E[M];
int vis[N];
bool flag;

void add(int a, int b, int c)
{
    E[idx].to = b;
    E[idx].w = c;
    E[idx].ne = h[a];
    h[a] = idx++;
}

ll dfs(int u)
{
    if(u == n)
    {
        flag = true;
        return 0;
    }
    if(vis[u])return vis[u];

    ll ans = -INF;
    for(int i = h[u];~i;i = E[i].ne)
    {
        int j = E[i].to;
        ans = max(dfs(j) + E[i].w, ans);
    }   
    vis[u] = ans;
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 1;i <= m;i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    ll ans = dfs(1);
    if(flag)cout << ans;
    else cout << -1;
}