cycle_finding.cpp

#include <bits/stdc++.h>
//Author : ritchie_s
#define for0(i, n) for (int i = 0; i < (int)(n); ++i) // 0 based indexing
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i) // 1 based indexing
// Short hand for usual tokens
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sp " "
// Shorthand for commonly used types
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;
// functions
#define MOD 1000000007
ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return (a/gcd(a,b))*b; }
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool prime(ll a) { if (a==1) return 0; for (int i=2;i<=round(sqrt(a));++i) if (a%i==0) return 0; return 1; }
// int gcd = __gcd(a,b) , ll LCM = 1LL*a*b/gcd
//solver fn
void solve(){
    ll n , m;
    cin>>n>>m;
    vvll edges;
    for0(i,m){
        ll u , v , wt;
        cin>>u>>v>>wt;
        edges.pb({u,v,wt});
    }
    vll dist(n+1 , 0);
    vll parent(n+1);
    dist[1] = 0;

    for(int i = 1 ; i<=n ; i++){
        for(auto x : edges){
            if(dist[x[0]] + x[2] < dist[x[1]]){
                dist[x[1]] = dist[x[0]] + x[2] ;
                parent[x[1]] = x[0];
            }
        }
    }

    int flag = 0;
    int nodeincycle = -1;
    for(auto x : edges){
        if(dist[x[0]] == LLONG_MAX)continue;
        if(dist[x[0]] + x[2] < dist[x[1]]){
            flag = 1;
            nodeincycle = x[1];
            parent[x[1]] = x[0];
            break;
        }
    }

    if(flag == 0){
        cout<<"NO"<<endl;
        return;
    }

    cout<<"YES"<<endl;
    for(int i = 1 ; i<=n ; i++){
        nodeincycle = parent[nodeincycle];
    }

    vll cycle;
    ll curr = nodeincycle;
    while (true) {
        cycle.pb(curr);
        curr = parent[curr];
        if (curr == nodeincycle) {
            cycle.pb(curr); // close the cycle
            break;
        }
    }

    reverse(all(cycle));

    for(auto x : cycle){
        cout<<x<<sp;
    }
    
        
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
     int t =1;
    
     while(t--){
        solve();
     }
    return 0;
}