#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>
#include <stack>
#include <set>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");


//clasa de multimi disjuncte folosita la algoritmul lui Kruskal
class DisjointSets
{
private:
    int n; //numarul de noduri
    vector<int> rep; //vectorul de reprezentanti(conform cursului)
    vector<int> h; //vector ce va retine inaltimile arborilor

public:
    DisjointSets(int n);//constructor parametrizat care face si initializarea vectorului de preprezentanti
    int Reprezentant(int x);//metoda ce returneaza reprezentantul unui nod x dat
    void Reuniune(int x, int y);//metoda ce reuneste arborii care contin nodurile x si y

};

DisjointSets::DisjointSets(int n)
{
    this->n = n;
    //initializam vectorul de reprezentanti si pe cel de inaltimi
    rep.resize(n+1);
    h.resize(n+1);
    for(int i=1; i<=n; ++i)
        rep[i] = i;
};

int DisjointSets::Reprezentant(int x)
{
    //daca x este chiar radacina(el este reprezentantul sau)
    if(x == rep[x])
        return x;
    else //altfel reprezentantul lui x va fi reprezentantul tatalui sau(apel recursiv)
    {
        //efectuam compresia asupra arborelui
        int r = Reprezentant(rep[x]); //aflu reprezentantul parintelui lui x
        rep[x] = r;
        return r;
    }
}

void DisjointSets::Reuniune(int x, int y)
{
    //aflam rep lui x si y
    int rx = Reprezentant(x);
    int ry = Reprezentant(y);

    //daca x si y au acelasi reprezentant, atunci acestia sunt deja in aceeasi multime(nu am ce sa reunesc)
    if(rx == ry)
        return;

    //subordonez reprezentantul din arborele cu inaltime mai mica reprezentantului din arborele cu inaltime mai mare
    if(h[rx] < h[ry])
        rep[rx] = ry;
    else if(h[rx] > h[ry])
        rep[ry] = rx;
    else //au inaltimi egale caz in care inaltimea creste cu 1 dupa subordonare
    {
        rep[rx] = ry;
        h[ry]++;
    }

}



class Graf
{
private:
    //strucutra unei muchii din graf(folosita in medota Biconexe)
    struct muchie
    {
        int x,y;
        muchie(int a, int b)
        {
            x=a;
            y=b;
        }
        muchie(){}
    };
    //strucutra unei muchii cu cost din graf(folosita in medota Kruskal)
    struct muchie_cost
    {
        int x,y,cost;
        muchie_cost(int a, int b, int c)
        {
            x=a;
            y=b;
            cost=c;
        }
        muchie_cost(){}
        bool operator < (const muchie_cost &m) const //operator pentru compararea costurilor a doua muchii
        {return cost < m.cost;}
    };
    int n; //nr de noduri
    int m; //nr de muchii
    vector<vector<int>> la; //vector cu listele de adiacenta
    vector<muchie_cost> vmc; //vector de muchii cu cost
    bool tip; //variabila care ne spune daca graful este orientat sau nu(daca este orientat este true altfel este false)
    void dfs_mc(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int>> &result);//subprogram de tip dfs folosit de metoda Muchii_critice
    void dfs_bcx(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int>> &biconexe); //subprogram de tip dfs folosit de metoda Biconexe
    void dfs_ctc(int x, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int>> &tareconexe);//subprogram de tip dfs folosit de metoda Componente_Tare_Conexe

public:
    Graf(int n, int m, bool tip);//constructor parametrizat care primeste si tipul grafului: orientat(true) sau neorientat(false)
    void Add_edge(int x, int y); //metoda de adaugare a unei muchii in graf
    void Add_edge_c(int x, int y, int c); //metoda de adaugare a unei muchii cu cost in graf
    void dfs(int x, vector<bool> &vizitat); //dfs = parcurgere dfs ce pleaca din nodul x si afiseaza vectorul parcurgerii(primeste ca parametru si un vector in care marcheaza nodurile vizitate)
    void bfs(int x, vector<bool> &vizitat);//bfs = parcurgere bfs ce pleaca din nodul x si afiseaza vectorul parcurgerii(primeste ca parametru si un vector in care marcheaza nodurile vizitate)
    void SortareTop(); //sortarea topologica a grafului(daca acesta este orientat si aciclic); afiseaza vectorul sortarii
    void Biconexe(); //metoda ce afiseaza vectorul de componente biconexe(care sunt vectori de noduri) ale grafului
    void Muchii_critice(); //metoda ce afiseaza vectorul de muchii critice(care sunt vectori cu 2 elemente) ale grafului
    void Componente_Tare_Conexe(); //metoda ce afiseaza vectorul de componente  tareconexe
    void Kruskal();//metoda ce implementeaza algoritmul lui Kruskal de determinare a APM-ului

};


Graf::Graf(int n, int m, bool tip)
{
    this->n = n;
    this->m = m;
    this->tip = tip;
    la.resize(n+1);
}


void Graf::Add_edge(int x, int y)
{
    la[x].push_back(y);
    if(!tip)
        la[y].push_back(x);
}

void Graf::Add_edge_c(int x, int y, int c)
{
    vmc.push_back(muchie_cost(x,y,c));
}

void Graf::dfs(int x, vector<bool> &vizitat)
{

    assert(vizitat.size()>=n);//verific daca vetorul dat ca parametru are dimensiunea corespunzatoare
    vizitat[x] = true;
    std::cout << x << " ";
    for(int i=0; i<la[x].size(); ++i)
    {
        int y = la[x][i];
        if (vizitat[y] == false)
            dfs(y, vizitat);
    }
}

void Graf::bfs(int x, vector<bool> &vizitat)
{
    assert(vizitat.size()>=n);//verific daca vetorul dat ca parametru are dimensiunea corespunzatoare
    queue<int> q;
    q.push(x);
    vizitat[x]=1;

    while(!q.empty())
    {
        x = q.front();
        std::cout << x << " ";
        q.pop();
        for(int i=0; i<la[x].size(); ++i)
        {
            int y=la[x][i];
            if(!vizitat[y])
            {
                q.push(y);
                vizitat[y]=true;
            }
        }
    }
}

void Graf::SortareTop()
{
    if(tip == false)
    { cout << "Metoda SortareTop este folosita doar la grafurile orientate aciclice!\n";
        return;
    }

    cout<< "Sortarea topologica a grafului dat este: ";

    //completam vector in care retinem gradele interioare ale nodurilor
    vector<int> gr_int(n+1);
    for(int i=1; i<=n; ++i)
    {
        for(int j=0; j<la[i].size(); ++j)
            ++gr_int[la[i][j]];
    }

    queue<int> q; //coada folosita la sortarea topologica
    //parcurgem vectorul de grade si punem in coada nodurile cu gradul interior 0
    for(int i=1; i<=n; ++i)
        if(gr_int[i]==0)
            q.push(i);

    //parcurgem coada pentru a obtine o sortare topologica
    while(!q.empty())
    {
        int x;
        //extragem un nod din coada
        x = q.front();
        q.pop();
        //scadeam gradele interioare ale nodurilor in care intra nodul curent
        for(int i=0; i<la[x].size(); ++i)
        {
            int y = la[x][i];
            --gr_int[y];
            if(gr_int[y] == 0)
                q.push(y);
        }
        cout << x << " ";
    }

}

void Graf::dfs_bcx(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int>> &biconexe)
{

    vizitat[x] = 1;
    moment[x] = timp++;
    low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int z = la[x][i];

        if (vizitat[z] == 0)
        {
            stiva.push(muchie(x,z));//adaug muchia in stiva de muchii
            dfs_bcx(z, x, vizitat, moment, low, stiva, timp, biconexe);

            //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
            // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
            if(low[x] > low[z])
                low[x] = low[z];


            //determinare componente biconexe
            if(moment[x] <= low[z]) //deci x este punct critic
            {
                set<int> componenta;
                int a, b; //capetele unei muchii
                do
                {
                    muchie m=stiva.top();
                    stiva.pop();
                    a=m.x;
                    b=m.y;
                    componenta.insert(a);
                    componenta.insert(b);
                }while(a!=x || b!=z);
                biconexe.push_back(componenta);//adaug componenta in vectorul de componente biconexe
            }

        }
        else //am dat de o muchie de intoarcere
        {
            if(z!=parinte) //verific ca z sa nu fie parinte al lui x
            {    //daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
                // strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
                // (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
                if (low[x] > moment[z])
                    low[x] = moment[z];
            }
        }
    }
}

void Graf::Biconexe()
{

    if(tip == true)
    { cout << "Metoda Biconexe este folosita doar la grafurile neorientate!\n";
        return;
    }

    vector<bool> vizitat(n+1); //vector vizitat
    vector<int> moment(n+1); //vector ce retine momentul  in care se viziteaza prima oara un nod di graf
    vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
    stack<muchie> stiva; //stiva in care vom retine muchiile unei componente biconeexe
    vector<set<int>> biconexe; //vectorul de componente biconexe

    int timp = 0;// timp = contor de timp pentru crearea vectorului moment

    //daca graful nu este conex, se analizeaza fiecare componenta conexa
    for(int i=1; i<=n; ++i)
        if(!vizitat[i])
            dfs_bcx(i,0,vizitat,moment,low,stiva, timp, biconexe);

    cout << "Numarul de componente biconexe: " << biconexe.size() << "\n";
    cout<< "Componentele biconexe sunt: \n";
    for(int i=0; i<biconexe.size(); ++i)
    {
        cout << i+1 << ") ";
        for(set<int>::iterator it=biconexe[i].begin(); it!=biconexe[i].end(); ++it)
            cout << *it << " ";
        cout << "\n";
    }
}

void Graf::dfs_mc(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int>> &result)
{
    vizitat[x] = 1;
    moment[x] = timp++;
    low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int z = la[x][i];

        if (vizitat[z] == 0)
        {
            dfs_mc(z, x, vizitat, moment, low, timp, result);

            //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
            // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
            if(low[x] > low[z])
                low[x] = low[z];


            //daca este muchie critica o adaugam in result
            if(low[z] > moment[x])
                result.push_back({x,z});

        }
        else //muchie de intoarcere
        {
            if(z!=parinte && low[x] > moment[z])
            {
                low[x] = moment[z];
            }
        }
    }
}

void Graf::Muchii_critice()
{
    if(tip == true)
    { cout << "Metoda Muchii_critice este folosita doar la grafurile neorientate!\n";
        return;
    }

    vector<bool> vizitat(n+1); //vector vizitat
    vector<int> moment(n+1); //vector ce retine momentul  in care se viziteaza prima oara un nod di graf
    vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
    vector<vector<int>> result; //vectorul de componente biconexe

    int timp = 0;// timp = contor de timp pentru crearea vectorului moment

    //daca graful nu este conex, se analizeaza fiecare componenta conexa
    for(int i=1; i<=n; ++i)
        if(!vizitat[i])
            dfs_mc(i,0,vizitat,moment,low, timp, result);


    cout << "Numarul de muchii critice: " << result.size() << "\n";
    cout << "Muchiile critice sunt: \n";
    for(int i=0; i<result.size(); ++i)
    {
        cout << i+1 << ") " << result[i][0] << " " << result[i][1] <<"\n";
    }
}

void Graf::dfs_ctc(int x, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int>> &tareconexe)
{
    vizitat[x] = 1;
    moment[x] = timp++;
    low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)

    stiva.push(x);//adaug nodul in stiva de noduri si in multimea care tine evidenta nodurilor din stiva
    in_stack.insert(x);

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int z = la[x][i];

        if (vizitat[z] == 0)
        {
            dfs_ctc(z, vizitat, moment, low, stiva, in_stack, timp, tareconexe);

            //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
            // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
            if(low[x] > low[z])
                low[x] = low[z];

        }
        else if(in_stack.find(z)!=in_stack.end())//am dat de o muchie de intoarcere si nodul z face parte din noua componenta tare_conexa
        {
            //daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
            // strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
            // (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
            if (low[x] > moment[z])
                low[x] = moment[z];
        }
    }
    if(low[x]==moment[x]) //daca nodul e radacina in componenta tare_conexa curenta(am avut un circuit)
    {
        set<int> componenta;
        int y;
        do{
            y=stiva.top();
            stiva.pop();
            in_stack.erase(y);
            componenta.insert(y);
        }while(y!=x);
        tareconexe.push_back(componenta);
    }
}

void Graf::Componente_Tare_Conexe()
{
    if(tip == false)
    { cout << "Metoda Componente_Tare_Conexe este folosita doar la grafurile orientate!\n";
        return;
    }
    vector<bool> vizitat(n+1);
    vector<int> moment(n+1); //vector ce retine momentul  in care se viziteaza prima oara un nod di graf
    vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
    stack<int> stiva; //stiva in care vom retine nodurile unei componente tare-conexe
    set<int> in_stack;//multimne care retine ce elemente sunt in stiva la un anumit moment
    vector<set<int>> tareconexe; //vectorul de componente tare-conexe
    int timp=0;

    //daca graful nu este conex, se analizeaza fiecare componenta tare-conexa
    for(int j=1; j<=n; ++j)
        if(vizitat[j]==0)
            dfs_ctc(j, vizitat, moment, low, stiva, in_stack, timp, tareconexe);

    cout << "Numarul de componente tareconexe: "<< tareconexe.size() << "\n";
    cout<< "Componentele tareconexe sunt: \n";
    for(int i=0; i<tareconexe.size(); ++i)
    {
        cout << i+1 << ") ";
        for(set<int>::iterator it=tareconexe[i].begin(); it!=tareconexe[i].end(); ++it)
            cout << *it << " ";
        cout << "\n";
    }

}

void Graf::Kruskal()
{
    //sortam vectorul de muchii crescator dupa cost(in M*logM)
    sort(vmc.begin(), vmc.end());

    //definim o padure de multimi disjuncte
    DisjointSets dj(n);

    vector<muchie> rezultat;//vectorul in care vom retine muchiile APM-ului
    rezultat.resize(n-1);//APM-ul va avea exact n-1 muchii(pt ca este arbore)

    int contor = 0;//variabila care retine cate muchii au fost selectate pana la un anumit moment de timp
    int cost_total = 0;

    for(int i=0; i<m; ++i)
    {
        //obtin extremitatiile muchiei curente
        int x = vmc[i].x;
        int y = vmc[i].y;

        //aflu reprezentatntii lui x si y(pt a vedea daca sunt sau nu in multimi disjuncte)
        int rx = dj.Reprezentant(x);
        int ry = dj.Reprezentant(y);

        //au acelasi reprezentant muchia nu este buna si trec mai departe
        if(rx == ry)
            continue;

        //adaug muchia curenta in rezultat(in APM)
        rezultat[contor] = muchie(x,y);
        contor++;
        cost_total+=vmc[i].cost;

        //daca am atins numarul de muchii necesare APM-ului ne oprim
        if(contor == n-1)
            break;

        //reunim multimiile lui x si y
        dj.Reuniune(x,y);
    }
    //afisam rezultatul(APM-ul)
    fout << cost_total << "\n";
    fout << n-1 << "\n";
    for(int i=0; i<contor; ++i)
        fout << rezultat[i].x << " " << rezultat[i].y << "\n";

}


int main()
{
    int n,m;
    int x,y,c;//capetele muchiei si costul
    fin >> n >> m; //citim datele
    //definim graful neorientat
    Graf G(n,m,0);
    //citim si adaugam in graf muchiile cu cost
    for(int i=0; i<m; ++i)
    {
        fin >> x >> y >> c;
        G.Add_edge_c(x,y,c);
    }

    //apelam metoda Kruskal pt a determina APM-ul asociat grafului
    G.Kruskal();

    return 0;
}