/*Prin adăugare succesivă de muchii, astfel încât mulțimea de muchii
selectate:
să aibă costul cât mai mic
să fie submulțime a mulțimii muchiilor unui arbore parțial de cost minim
(apcm)
Cum selectăm ușor o muchie: trb sa fie de cost minim si sa
unesca doua componente (nu formeze cicluri cu componentele deja selectate)
*/

#include<iostream>
#include<fstream>
#include <algorithm>
using namespace std;

ifstream f ("apm.in");
ofstream g ("apm.out");

struct abc{
int na;
int nb;
int cost;
}v[1000005],sol[1000005];;
int tata[1000005];

int compare(abc x,abc y)
{
    return x.cost<y.cost;
}

int Reprez(int u) //Reprez(u) - returnează reprezentantul componentei care conține pe u
{
    int cop=u;
    while(tata[u]!=0)
    {
        u=tata[u];
    }
    while(tata[cop]!=0)
    {
        int aux=cop;
        cop=tata[cop];
        tata[aux]=u;
    }
    return u;
}

void Reuneste(int u, int w) //Reunește(u,v) - unește componenta care conține u cu cea care conține w
{
    tata[u]=w;
}




int main()
{
  int N,M;
  f>>N>>M;

 for(int i=1;i<=M;++i)
    {
    int a,b,c;
        f>>a>>b>>c;
        v[i].na=a;
        v[i].nb=b;
        v[i].cost=c;
    } //am creat toate muchiile de la a la b cu cost c

    sort(v+1,v+M+1,compare); //Pentru a selecta ușor o muchie de cost minim cu proprietatea dorită,
                             //ordonăm crescător muchiile după cost și considerăm muchiile în
                             //această ordine.


    int nrapcm=0,cm=0;//numarul de muchii adaugate la apcm si costul acestuia

    for(int i=1;i<=M;++i)
    {
        int x=Reprez(v[i].na);
        int y=Reprez(v[i].nb);

        if(x!=y) //nu formeaza ciclu
        {
            nrapcm++; //creste numarul de muchii adaugate la apcm
            Reuneste(x,y); //reuneste componenta care conține x cu cea care conține y
            sol[nrapcm]=v[i];//adauga la solutie muchia

            cm=cm+v[i].cost; //calculeaza costul apcm
        }

        if(nrapcm==N-1) //n-1 muchii adaugate rezulta arbore finalizat
            break;
    }

    g<<cm<<'\n';
    g<<N-1<<'\n';//scrie costul minim si nr de muchii al arborelui partial selectat


    for(int i=1;i<=nrapcm;++i) //scrie capetele muchiilor ce apartin arborelui solutie
    {
        g<<sol[i].na<<" "<<sol[i].nb<<'\n';

    }
    return 0;
}