#include <bits/stdc++.h>

using namespace std;
/*
string VerifyHakimi(int num, vector<int>&vec){
        fin>>n;
        for(;n!=0;n--)
        {
            int x;
            fin>>x;
            vec.push_back(x);
        }
        while(1){
            sort(vec.begin(),vec.end(),greater<>());
 
            if(vec[0] == 0)
                return "Graful se poate construi\n";
            int size_prim = vec[0];
            vec.erase(vec.begin()+0);
 
            if(size_prim > vec.size())
                return "Graful NU se poate construi\n";
 
            for(int i=0;i<size_prim;i++){
                vec[i]--;
                if(vec[i]<0)
                    return "Graful NU se poate construi\n";
            }
        }
    }
};
*/

const int N = 100010;

class Graf
{
private:
    int noduri, muchii;

    void dfs(int start, vector<int> v[N], vector<int> &viz);
    void dfs_biconexe(int, int, vector<int> *, vector<int> *, vector<int> &, vector<int> &, vector<int> &, vector<int> &, int &, int &);

    void dfs_1(int, vector<int> &, vector<int> &, vector<int> *);
    void dfs_2(int, vector<int> &, vector<int>*, vector<int> *, int &);

public:
    Graf(int, int);
    void add_edge(int x, int y);
    int nr_connected_components(vector<int> v[N], vector<int> &viz);
    void bfs(ifstream &, ofstream &, queue<pair<int, int>>, vector<int> *, vector<int> &, vector<int> &, int);

    void solve_biconexe(vector<int> *, vector<int> *, vector<int> &, vector<int> &, vector<int> &, vector<int> &, int &, int &);
    void solve_CTC(vector<int> *, vector<int> *, vector<int> *, vector<int> &, vector<int> &, vector<int> &, int &);

    
};


class Disjoint_set
{
private:
    int noduri, muchii;
    int find_root(int,vector<int>&);
    void unite(int,int,vector<int> &, vector<int> &);

public:
    Disjoint_set(int);
    void solve_paduri_de_multimi_disjuncte(ifstream &, ofstream &, vector<int>&, vector<int> &);
    void solve_APM(ifstream &fin, ofstream &fout, vector<int>&, vector<int>&, vector<pair<int,int>>, vector<tuple<int,int,int>>);
};

void Disjoint_set::solve_APM(ifstream &fin, ofstream &fout, vector<int> &rang, vector<int> &tati,vector<pair<int,int>> ans, vector<tuple<int,int,int>> t)
{
    int mincost = 0;
    for(auto edge : t)
    {
        if(get<0>(edge) == -1)
            continue;
        
        int x_root = find_root(get<0>(edge),tati);
        int y_root = find_root(get<1>(edge),tati);

        if(x_root != y_root)
        {
            unite(x_root, y_root,tati,rang);
            mincost += (get<2> (edge));
            ans.push_back(make_pair((get<0>(edge)), (get<1>(edge))));
        }
    }

       fout << mincost << '\n'
         << ans.size() << '\n';
 
    for (auto it : ans)
        fout << it.second << " " << it.first << '\n';
}

void Disjoint_set :: solve_paduri_de_multimi_disjuncte(ifstream &fin, ofstream &fout,vector<int> &rang, vector<int> &tati)
{
    int m;
    fin>>m;
    //cout<<m;
    for(int i=1;i<= m; i++)
    {
        rang[i] = 1;
        tati[i] = i;
    }
    for(int i=1; i<=m;i++)
    {
        int op,x,y;
        fin>>op>>x>>y;
        if(op == 1)
            unite(x,y,tati,rang);
        else
            if(find_root(x,tati) == find_root(y,tati))
                fout<<"DA\n";
            else
                fout<<"NU\n";
    }
}
Disjoint_set:: Disjoint_set(int n)
{
    this-> noduri = noduri;
}

int Disjoint_set::find_root(int x, vector<int>&tati)
{
    while(tati[x] != x)
        x=tati[x];
    return x;
}

void Disjoint_set::unite(int x, int y,vector<int> &tati,vector<int> &rang)
{
    int rad_x = find_root(x,tati);
    int rad_y = find_root(y,tati);

    if(rang[rad_x] >= rang[rad_y])
    {
        tati[rad_y] = rad_x;
        rang[rad_x] += rang[rad_y];
    }
    else
    {
        tati[rad_x] = rad_y;
        rang[rad_y] +=rang[rad_x];
    }
}

void Graf::solve_CTC(vector<int> nxt[N], vector<int> ans[N], vector<int> prv[N], vector<int> &viz_1, vector<int> &viz_2, vector<int> &top, int &nr_ans)
{
    for (int i = 1; i <= this->noduri; i++)
        if (!viz_1[i])
            dfs_1(i, viz_1, top, nxt);

    reverse(top.begin(), top.end());

    for (auto it : top)
        if (!viz_2[it])
        {
            nr_ans++;
            dfs_2(it, viz_2, ans, prv, nr_ans);
        }
/*
    fout << nr_ans << '\n';

    for(int i=0;i<nr_ans;i++)
        {
            for(auto it: ans[i])
                fout<<it<<" ";
            fout<<'\n';
        }
*/
/*
    for ( auto it : ans)
    {
        for (auto elem : it)
            fout << elem << " ";
        fout << '\n';
    }
    */
}

void Graf::dfs_1(int node, vector<int> &viz_1, vector<int> &top, vector<int> nxt[N])
{
    viz_1[node] = 1;
    for (auto it : nxt[node])
        if (!viz_1[it])
            dfs_1(it, viz_1, top, nxt);
    top.push_back(node);
}

void Graf::dfs_2(int node, vector<int> &viz_2, vector<int> ans[N], vector<int> prv[N], int &nr_ans)
{
    viz_2[node] = 1;

    ans[nr_ans].push_back(node);

    for (auto it : prv[node])
        if (!viz_2[it])
            dfs_2(it, viz_2, ans, prv, nr_ans);
}

void Graf::dfs_biconexe(int nod, int tata, vector<int> adj[N], vector<int> ans[N], vector<int> &intoarcere, vector<int> &viz, vector<int> &st, vector<int> &nivel, int &top, int &nr_sol)
{
    intoarcere[nod] = nivel[nod] = nivel[tata] + 1;
    viz[nod] = 1;
    top++;
    st[top] = nod;

    for (auto fiu : adj[nod])
    {
        if (fiu == tata)
            continue;
        if (viz[fiu])
        {
            intoarcere[nod] = min(intoarcere[nod], nivel[fiu]);
            continue;
        }

        dfs_biconexe(fiu, nod, adj, ans, intoarcere, viz, st, nivel, top, nr_sol);

        intoarcere[nod] = min(intoarcere[nod], intoarcere[fiu]);

        if (intoarcere[fiu] >= nivel[nod])
        {
            nr_sol++;
            while (st[top + 1] != fiu)
            {
                ans[nr_sol].push_back(st[top]);
                top--;
            }
            ans[nr_sol].push_back(nod);
        }
    }
}
void Graf::solve_biconexe(vector<int> adj[N], vector<int> ans[N], vector<int> &intoarcere, vector<int> &viz, vector<int> &st, vector<int> &nivel, int &top, int &nr_sol)
{
    for (int i = 1; i <= this->noduri; i++)
        if (!viz[i])
            dfs_biconexe(i, 0, adj, ans, intoarcere, viz, st, nivel, top, nr_sol);
}
void Graf::bfs(ifstream &fin, ofstream &fout, queue<pair<int, int>> q, vector<int> adj[N], vector<int> &viz, vector<int> &ans, int nod_cerut)
{
    while (!q.empty())
    {
        pair<int, int> dp = q.front();
        int x = dp.first;
        int y = dp.second;
        ans[x] = y;
        for (auto it : adj[x])
            if (!viz[it])
            {
                viz[it] = 1;
                q.push(make_pair(it, y + 1));
            }
        q.pop();
    }

    for (int i = 1; i <= this->noduri; i++)
    {
        if (ans[i] == 0 && i != nod_cerut)
            ans[i] = -1;
        fout << ans[i] << " ";
    }
}

Graf::Graf(int n, int m)
{
    (*this).noduri = n;
    (*this).muchii = m;

    std::cout << "Constructor " << n << " " << m << '\n';
}

void Graf::dfs(int start, vector<int> v[N], vector<int> &viz)
{
    viz[start] = 1;
    for (auto it : v[start])
        if (!viz[it])
            dfs(it, v, viz);
}

int Graf::nr_connected_components(vector<int> v[N], vector<int> &viz)
{
    int ct = 0;
    for (int i = 1; i <= (this->noduri); i++)
        if (!viz[i])
        {
            dfs(i, v, viz);
            ct++;
        }
    return ct;
}

int comp(tuple<int, int, int> a, tuple<int, int, int> b)
{
    return ((get<2>(a)) < (get<2>(b)));
}

int main()
{
    int problema = 6;
    if(problema == 6)
    {
        ifstream fin("apm.in");
        ofstream fout("apm.out");
        int n,m;
        vector<tuple<int,int,int>> t = {};
        vector<int> root = {}, tati = {};
        vector<pair<int,int>> ans = {};
        t.push_back(make_tuple(-1,-1,-1));
        root.push_back(-1);
        tati.push_back(-1);
        fin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            int x,y,cost;
            fin>>x>>y>>cost;
            t.push_back(make_tuple(x,y,cost));            
        }
    sort(t.begin(),t.end(),comp);

    for(int i=1;i<=n;i++)
        {
            root.push_back(i);
            tati.push_back(i);
        }

        Disjoint_set G(n);
        G.solve_APM(fin,fout,root,tati,ans,t);
    }
    if(problema == 5)
    {
        ifstream fin("disjoint.in");
        ofstream fout("disjoint.out");
        vector<int> tati(N,0), rang(N,0);
        int n,m,op;
        fin>>n;
        Disjoint_set G(n);
        G.solve_paduri_de_multimi_disjuncte(fin,fout,rang,tati);

    }
    if (problema == 4)
    {
        ifstream fin("ctc.in");
        ofstream fout("ctc.out");

        int n, m;
        fin >> n >> m;

        vector<int> adj[n + 5];
        vector<int> viz_1(n + 5, 0), viz_2(n + 5, 0);
        vector<int> nxt[n + 5] = {};
        vector<int> prv[n + 5] = {};
        vector<int> ans[n + 5] = {};
        vector<int> top;

        int nr_ans = 0;

        for (int i = 1; i <= m; i++)
        {
            int x, y;
            fin >> x >> y;
            nxt[x].push_back(y);
            prv[y].push_back(x);
        }

        Graf G(n, m);
        G.solve_CTC(nxt,ans,prv,viz_1,viz_2,top,nr_ans);

        fout << nr_ans;

    for(int i=0;i<=nr_ans;i++)
        {
            for(auto it: ans[i])
                fout<<it<<" ";
            fout<<'\n';
        }

    }

    if (problema == 3)
    {
        ifstream fin("biconex.in");
        ofstream fout("biconex.out");

        int n, m;
        fin >> n >> m;

        vector<int> adj[n + 5];
        vector<int> viz(n + 5, 0);
        vector<int> ans[n + 5] = {};
        vector<int> intoarcere(n + 5, 0);
        vector<int> nivel(n + 5, 0);
        vector<int> st(n + 5, 0);

        int top = 0, nr_sol = 0;

        for (int i = 1; i <= m; i++)
        {
            int x, y;
            fin >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }

        Graf G(n, m);
        G.solve_biconexe(adj, ans, intoarcere, viz, st, nivel, top, nr_sol);

        fout << nr_sol << '\n';
        for (int i = 1; i <= nr_sol; i++)
        {
            for (auto it : ans[i])
                fout << it << " ";
            fout << '\n';
        }
    }
    if (problema == 2)
    {
        ifstream fin("bfs.in");
        ofstream fout("bfs.out");
        int n, m, nc;
        fin >> n >> m >> nc;

        vector<int> adj[n + 5] = {};
        vector<int> viz(n + 5, 0);
        vector<int> ans(n + 5, 0);
        queue<pair<int, int>> q = {};
        // for(auto it:viz)
        //     cout<<it<<" ";
        // cout<<'\n';

        for (int i = 1; i <= m; i++)
        {
            int x, y;
            fin >> x >> y;
            if (x != y)
                adj[x].push_back(y);
        }
        /*
        for(int i=1;i<=n;i++)
        {
            cout<<i<<" : ";
            for(auto it:adj[i])
                cout<<it<<" ";
            cout<<'\n';
        }
        cout<<"---------------\n";
        */
        q.push(make_pair(nc, 0));
        viz[nc] = 1;

        Graf G(n, m);
        G.bfs(fin, fout, q, adj, viz, ans, nc);
    }
    if (problema == 1)
    {
        ifstream fin("dfs.in");
        ofstream fout("dfs.out");
        int n, m;
        fin >> n >> m;
        vector<int> adj[n + 5] = {};
        vector<int> viz(n + 5, 0);
        for (auto it : viz)
            std::cout << it << " ";
        std::cout << '\n';
        for (int i = 1; i <= m; i++)
        {
            int x, y;
            fin >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        for (int i = 1; i <= n; i++)
            if (adj[i].size())
            {
                std::cout << i << " : ";
                for (auto it : adj[i])
                    std::cout << it << " ";
                std::cout << '\n';
            }
        std::cout << "-----------------\n\n";

        Graf G(n, m);
        fout << G.nr_connected_components(adj, viz);
    }

    return 0;
}