//Arbore partial de cost minim (Kruskal)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int n,m,s;
struct muchie{
    int n1,n2,c;
    bool used;
}mch[400005],aux;
int M[200005]; //M[i] - retine multimea in care se afla nodul i
struct multime{
    int nod;
    struct multime *urm;
}*L[200005],*act;

void citire()
{
    in>>n>>m;
    for(int i=1;i<=m;++i)
        in>>mch[i].n1>>mch[i].n2>>mch[i].c;
}

void quicksort(int st,int dr)
{
    int i=st,j=dr;
    muchie mij=mch[st+(dr-st)/2];

    do{
        while(i<dr && mch[i].c<mij.c)
            ++i;
        while(j>st && mch[j].c>mij.c)
            --j;
        if(i<=j)
        {
            aux=mch[i], mch[i]=mch[j], mch[j]=aux;
            ++i, --j;
        }
    }while(i<=j);

    if(i<dr) quicksort(i,dr);
    if(j>st) quicksort(st,j);
}

void kruskal()
{
    int nr,a,b;
    s=nr=0;

    //la inceput fiecare nod e intr-o multime diferita
    for(int i=1;i<=n;++i)
        M[i]=i;

    //initilizeaza multimea listelor
    for(int i=1;i<=n;++i)
    {
        act=new multime;
        act->nod=i;
        act->urm=NULL;
        L[i]=act;
    }

    //ia fiecare muchie pe rand
    //pana cand avem n-1 muchii
    for(int i=1; i<=m && nr<n-1; ++i)
    {
        muchie x = mch[i];
        //daca nodurile se afla in multimi diferite -> foloseste muchia:
        //pune toate nodurile din multimea cu nr de ordine mai mare (b) in multimea cu nr de ordine mai mic (a)
        if(M[x.n1]!=M[x.n2])
        {
            if(M[x.n1]<M[x.n2])
                a=M[x.n1], b=M[x.n2];
            else
                a=M[x.n2], b=M[x.n1];
            /*
            for(int j=1;j<=n;++j)
                if(M[j]==b)
                    M[j]=a;
            */
            act=L[b];
            while(act->urm!=NULL)
            {
                M[act->nod]=a;
                act=act->urm;
            }
                M[act->nod]=a;
            act->urm=L[a];
            L[a]=L[b];
            L[b]=NULL;

            ++nr;   //creste numarul de muchii
            s+=x.c; //adauga costul muchiei la suma
            mch[i].used=1;
        }
    }
}

void afisare()
{
    out<<s<<"\n"<<n-1<<"\n";
    for(int i=1;i<=n;++i)
        if(mch[i].used==1)
            out<<mch[i].n1<<" "<<mch[i].n2<<"\n";
}

int main()
{
    citire();
    quicksort(1,m); //sorteaza muchiile crescator in functie de cost
    kruskal();
    afisare();

    return 0;
}