G. Велике крадівництво

#include <bits/stdc++.h>

#define int long long
#define pb push_back
#define mp make_pair
//#define ull long long

typedef unsigned long long ull;

using namespace std;

const int DEBUG = 0;
const int INF = ((int)1e15 + 10);
const int N = 100010;
const int md = (int)1e7 + 19;

vector<int> parent;
vector<int> deep;
vector<set<pair<int,int> > > rest;

void init(int n)
{
    parent.resize(n+1);
    deep.resize(n+1,0);
    rest.resize(n+1);
    for(int i = 0; i <= n; i++)
        parent[i] = i;
    return;
}

int find_parent(int x)
{
    if(x == parent[x])
        return x;
    return parent[x] = find_parent(parent[x]);
}

void union_sets(int a,int b)
{
    int A = find_parent(a);
    int B = find_parent(b);
    if(A == B)
    {
        rest[A].insert(mp(a,b));
        return;
    }
    if(deep[A] > deep[B])
    {
        for(auto x : rest[B])
            rest[A].insert(x);
        rest[B].clear();
        parent[B] = A;
        deep[A] = max(deep[A],deep[B]+1);
    }
    else
    {
        for(auto x : rest[A])
            rest[B].insert(x);
        rest[A].clear();
        parent[A] = B;
        deep[B] = max(deep[B],deep[A]+1);
    }
    return;
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n,m;
    cin >> n >> m;

    init(n);

    int a,b;

    for(int i = 0; i < m; i++)
    {
        cin >> a >> b;
        union_sets(a,b);
    }

    int cur = find_parent(1);

    vector<pair<pair<int,int>,int> > ans;

    pair<int,int> p;
    int t;

    for(int i = 1; i <= n; i++)
    {
        t = find_parent(i);
        if(t == cur)
            continue;
        if(rest[cur].size())
        {
            p = *rest[cur].begin();
            ans.pb(mp(p,t));
            rest[cur].erase(rest[cur].begin());
            union_sets(cur,t);
            cur = find_parent(i);
        }
        else if(rest[t].size())
        {
            p = *rest[t].begin();
            ans.pb(mp(p,cur));
            rest[t].erase(rest[t].begin());
            union_sets(cur,t);
            cur = find_parent(i);
        }
    }

    cout << ans.size() << "\n";
    for(auto x : ans)
    {
        cout << x.first.first << " " << x.first.second << " " << x.second << "\n";
    }

    return 0;
}