Shared code

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
#define sp(x) fixed << setprecision(x)
#define memo(a,b) memset(a,b,sizeof(a))


const ll N=100005;
vector<pair<ll, ll>> arr[N]; 
ll dist[N];
ll cnt[N]; 
ll n,m;
void dfs(ll i)
{
    cnt[i]=1e18;
    for(auto [v,x]:arr[i])
    if(cnt[v]!=1e18)dfs(v);
}

void run(ll src) {
        //priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
        queue<pair<ll, ll>>pq;
        dist[src] = 0;
        pq.push({0, src});
        while (!pq.empty()) {
            ll d = pq.front().first, u = pq.front().second;
            pq.pop();
            if(cnt[u]>n && cnt[u]!=1e18) dfs(u);
            if (d > dist[u] || cnt[u]>n) continue;
            for (auto &edge : arr[u]) {
                ll v = edge.first, w = edge.second;

                if (dist[v] > dist[u] + w){
                    dist[v] = dist[u] + w, pq.push({dist[v], v});
                    cnt[v]++;
                }
            }
        }
}



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

cin>>n;
for(ll i=0;i<=n;i++){dist[i]=1e18; cnt[i]=0;}
cin>>m;
for(ll i=0;i<m;i++)
{
    ll a,b,x; cin>>a>>b>>x;
    arr[a].push_back({b,-1*x});
}
run(1);
if(cnt[n]>n || dist[n]==1e18)dist[n]=1;
cout<<-dist[n]<<endl;

}