Heavy Cycle Edges UVA - 11747 || MST

#include<bits/stdc++.h>
using namespace std;

typedef long long           ll;
typedef unsigned long long  ull;
typedef double              ld;//%Lf
#define ff                  first
#define ss                  second
#define pb                  push_back
#define mp                  make_pair
#define ppb                 pop_back
#define in                  insert
#define sz(a)               int((a).size())
#define vi                  vector<int>
#define vl                  vector<ll>
#define vvi                 vector<vector<int> >
#define pii                 pair<int,int>
#define piii                pair<int,pair<int,int> >
#define pll                 pair<ll,ll>
#define vii                 vector<pii>
#define vll                 vector<pll>
#define viii                vector<piii>
#define YES                 cout << "YES\n"
#define NO                  cout << "NO\n"

#define scl(n)              scanf("%lld",&n)
#define scll(x,y)           scanf("%lld %lld",&x,&y)
#define gtl(x)              getline(cin, (x))

#define f0(b)               for(int i=0;i<(b);i++)
#define f00(b)              for(int j=0;j<(b);j++)
#define f1(b)               for(int i=1;i<=(b);i++)
#define f11(b)              for(int j=1;j<=(b);j++)
#define f2(a,b)             for(int i=(a);i<=(b);i++)
#define f22(a,b)            for(int j=(a);j<=(b);j++)
#define RFOR(i,x,y)         for(int i=x;i>=y;i--)
#define all(v)              v.begin(),v.end()
#define rall(v)             v.rbegin(),v.rend()
#define unq(v)              sort(all(v)),(v).resize(unique(all(v))-v.begin())
#define present(c,x)        ((c).find(x) != (c).end())
#define cpresent(c,x)       (find(all(c),x) != (c).end())
#define min_ele(v)          (*min_element(all(v)))
#define max_ele(v)          (*max_element(all(v)))
#define cnt_ele(v, x)       (count(all(v), x))
#define sum_ele(v)          (accumulate(all(v),0))
#define reversed(s)         reverse(s.begin(), s.end())

#define testcase            ll t; cin>>t; while (t--)
#define vout(v)             for(int ind=0;ind<v.size();ind++){ cout<<v[ind]; if(ind<v.size()-1) cout<<' '; else cout<<endl;}
#define arrout(arr,i,x,y)   for(int i=x;i<=y;i++){ cout<<arr[i]; if(i<y) cout<<' '; else cout<<endl;}
#define PI                  acos(-1)
#define CLR(x, y)           memset(x, y, sizeof(x))
#define Precision(a)        cout << fixed << setprecision(a)
#define BITCH_FAST()        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) //Don't use scanf/printf
#define MAXP                1000006
#define MOD                 1e9+7//10000007 // For big mod
#define EPS                 1e-7

template <typename T> T Sqr(T x) { T n = x * x ; return n ;}
template <typename T> T Pow(T B,T P){ if(P==0) return 1; if(P&1) return B*Pow(B,P-1);  else return Sqr(Pow(B,P/2));}
template <typename T> T Abs(T a) {if(a<0)return -a;else return a;}
template <typename T> T Gcd(T a,T b){if(a<0)return Gcd(-a,b);if(b<0)return Gcd(a,-b);return (b==0)?a:Gcd(b,a%b);} // better than __gcd
template <typename T> T Lcm(T a,T b) {if(a<0)return Lcm(-a,b);if(b<0)return Lcm(a,-b);return a*(b/Gcd(a,b));}
template <typename T> T power(T n, T p){ T res = 1;while(p > 0){if(p & 1)res *= n;n *= n;p >>= 1;}return res;}
template <typename T> T BigMod (T b,T p,T m){if (p == 0) return 1;if (p%2 == 0){T s = BigMod(b,p/2,m);return ((s%m)*(s%m))%m;}return ((b%m)*(BigMod(b,p-1,m)%m))%m;}
template <typename T> inline string ToBinary(T n) {string r ;while(n != 0) {r = ( n % 2 == 0 ? "0" : "1" ) + r ; n >>= 1;} return r ;}
long long BinaryToDecimal(string s) {int len = s.size();long long n = 0, p = 1;for (int i = len - 1; i >= 0; i-- , p *= 2) n += p * (s[i] - '0');return n;}
int Strtoint(string str){stringstream ss(str);int x = 0;ss >> x ;return x ;}
string Intostr(int x){stringstream ss; ss << x; string str = ss.str(); return str;}

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << endl;
        //use cerr if u want to display at the bottom
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif

/*----------------------Graph Moves----------------*/
int ROW[]={+1,-1,+0,+0};
int COL[]={+0,+0,+1,-1};

int X[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
int Y[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move

int KX[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
int KY[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
map<int, int>MP;
vi parent, raank;
viii edges;
void makeset(int n)
{
    for(int i=0; i<n; i++)
    {
        parent[i]=i;
        raank[i]=0;
    }
}
int find_parent(int v)
{
    if(parent[v]==v)
    {
        return v;
    }
    return parent[v]=find_parent(parent[v]);
}
void union_seet(int u, int v)//Join
{
    u=find_parent(u);
    v=find_parent(v);
    if(u!=v)
    {
        if(rand()%2)
        {
            swap(u, v);
        }
        parent[v]=u;
    }
}

void Kruskals(viii &edges, int n)
{
    sort(all(edges));
    vector<int>v;
    v.clear();
    for(auto e:edges)
    {
        int u=e.ss.ff;
        int v=e.ss.ss;
        int set_u=find_parent(u);
        int set_v=find_parent(v);
        if(set_u!=set_v)
        {
            union_seet(u,v);
            //wt+=e.ff;
            MP[e.ff]--;
            //trace(e.ff);

        }
    }
    for(auto ex:MP)
    {
        if(ex.ss)
        {
            while(ex.ss--)
            {
                v.pb(ex.ff);
            }
        }
    }
    if(sz(v)==0) cout << "forest\n";
    else
    {
        f0(sz(v))
        {
            if(i==sz(v)-1) cout << v[i] << endl;
            else cout << v[i] << " ";
        }
    }
}
int main()
{
    //BITCH_FAST();
    #ifdef FLAME
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ll n, m;
    while(cin >> n >> m, !(n==0 && m==0))
    {
        edges.clear();
        MP.clear();
        parent.resize(n);
        raank.resize(n);
        makeset(n);
        f0(m)
        {
            int a, b, x;
            cin >> a >> b >> x;
            MP[x]++;
            edges.push_back({x,{a, b}});


        }
        Kruskals(edges, m);
    }
    #ifdef FLAME
        fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}