You are given a directed weighted graph, and your task is to find out if it contains a negative cycle, and also give an example of such a cycle.

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
#define mod 1000000007 
#define check exit(0)
#define nl cout<<endl;
#define inp 30000
#define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define trace(x) cerr<<#x<<" : "<<x<<endl;
#define deb(v) for(int i=0;i<v.size();i++) {cout<<v[i]; (i==v.size()-1) ? cout<<"\n":cout<<" "; }
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
using namespace __gnu_pbds;
using namespace std;
 
vector<pair<ll,ll>> g[inp];
vector<ll> weight(inp,0); 
 
vector<bool> vis1(inp,false),vis2(inp,false);
vector<ll> par(inp);
vector<ll> ans;
 
void dfs(ll n,ll tot)
{
    vis1[n]=true;
    weight[n]=tot;
 
    for(pair<ll,ll> c:g[n])
    {
        if(vis1[c.first] && !vis2[c.first]) // cycle detected
        {
            ll tmp = weight[n]-weight[c.first] + c.second; //weight of cycle

            if(tmp<0)
            {   
                ans.push_back(c.first);
                while(n!=c.first)
                {
                    ans.push_back(n);
                    n=par[n];
                }
                ans.push_back(c.first);

                reverse(ans.begin(),ans.end());
                
                cout<<"YES\n";
                for(int x:ans) cout<<x<<" ";
                check;
            }
        }
        if(!vis1[c.first]) { par[c.first]=n; dfs(c.first , tot+c.second); }
    }
 
    vis2[n]=true; //completely explored node
}
 
int main()
{
    jaldi
 
    ll n,m; //vertices & edges
    cin>>n>>m;
 
    vector<vector<ll>> arr(n+1,vector<ll>(n+1,LLONG_MAX)); // adj. matrix so that we can select edge with 
                                                           // minimum weight
 
    for(ll i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        arr[u][v]=min(arr[u][v],w);
    }
 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(arr[i][j]<LLONG_MAX) { g[i].push_back({j,arr[i][j]}); } //preparing adj. list
        }
    }
 
    for(int i=1;i<=n;i++)
    {
        if(!vis1[i])
        {
            dfs(i,0);
        }
    }
 
    cout<<"NO\n"; //Neg. cycle not found
 
    return 0;
}