#include <iostream>
#include <fstream>

using namespace std;

class Graf
{
    unsigned long N, M;
    struct semi {unsigned long nod; short cost; semi *urm;};
    struct muchie {unsigned long nod1, nod2; short cost;};
    long cost;
    unsigned long tati[200001];
    semi * G[200001];
    void push (unsigned long unde, unsigned long nod, short C);
    void echilibrare1 (muchie *A, unsigned long nr);
    void echilibrare2 (muchie *A, unsigned long i, unsigned long nr);
    void decapitare (muchie *A, unsigned long &nr);
    //void afis (muchie *A, unsigned long nr);
public:
    Graf ();
    void citire();
    void prim (unsigned long r);
    void afisare ();
    ~Graf ();
};

/*void Graf::afis (muchie *A, unsigned long nr)
{
    unsigned long i;
    for (i=1; i<=nr; i++)
        cout<<A[i].nod1<<' '<<A[i].nod2<<' '<<A[i].cost<<'\n';
    cout<<'\n';
}*/

Graf::Graf ()
{
    unsigned long i;
    for (i=1; i<=200000; i++)
        G[i]=NULL;
}

Graf::~Graf()
{
    unsigned long i;
    semi *aux;
    for (i=1; i<=N; i++)
    {
        while (G[i]!=NULL)
        {
            aux=G[i]->urm;
            delete G[i];
            G[i]=aux;
        }
    }
}

void Graf::echilibrare2 (muchie *A, unsigned long i, unsigned long nr)
{
    if (nr>=i*2+1)
    {
        if (A[i*2+1].cost < A[i].cost || A[i*2].cost < A[i].cost)
        {
            muchie m;
            if (A[i*2+1].cost < A[i*2].cost)
            {
                m=A[i*2+1];
                A[i*2+1]=A[i];
                A[i]=m;
                echilibrare2 (A, i*2+1, nr);
            }
            else
            {
                m=A[i*2];
                A[i*2]=A[i];
                A[i]=m;
                echilibrare2 (A, i*2, nr);
            }
        }
    }
    else
    {
        if (i*2==nr && A[i*2].cost < A[i].cost)
        {
            muchie m;
            m=A[i*2];
            A[i*2]=A[i];
            A[i]=m;
        }
    }
}

void Graf::decapitare (muchie *A, unsigned long &nr)
{
    A[1]=A[nr];
    nr--;
    unsigned long i=1;
    echilibrare2 (A, i, nr);
}

void Graf::echilibrare1 (muchie *A, unsigned long nr)
{
    if (A[nr].cost < A[nr/2].cost && nr>1)
    {
        muchie m;
        m=A[nr];
        A[nr]=A[nr/2];
        A[nr/2]=m;
        echilibrare1 (A, nr/2);
    }
}

void Graf::push(unsigned long unde, unsigned long nod, short C)
{
    semi *s;
    s=new semi;
    s->cost=C;
    s->nod=nod;
    s->urm=G[unde];
    G[unde]=s;
}

void Graf::prim(unsigned long r)
{
    muchie A[N+1], m; //retinem muchiile care pot fi adaugate in nod1 avem nodul care apartine arborelui
    unsigned long i, x, nr=0;
    bool v[N+1];// a[i]==1 daca i apartine arborelui, 0 altfel
    semi *j;
    for (i=1; i<=N; i++)
        v[i]=0;
    v[r]=1;
    short c;
    cost=0;
    tati[r]=0;
    for (i=1; i<N; i++)//avem de ales N-1 muchii
    {
        //in r avem ultimul nod ales
        //cout<<r<<'\n';
        for (j=G[r]; j!=NULL; j=j->urm)//adaugam muchiile adiacente cu r
        {
            x=j->nod;
            if (v[x]!=1)//nodul adiacent trebuie sa nu fie deja in arbore
            {
                c=j->cost;
                nr++;
                m.cost=c;
                m.nod1=r;
                m.nod2=x;
                A[nr]=m;
                echilibrare1 (A, nr);
            }
        }
        //afis (A, nr);
        while (v[A[1].nod2]==1)
            decapitare (A, nr);
        //afis (A, nr);
        m=A[1];
        decapitare (A, nr);
        r=m.nod2;
        v[r]=1;
        tati[r]=m.nod1;
        cost+=m.cost;
        //afis (A, nr);
        //cout<<'\n';
    }
}

void Graf::citire()
{
    ifstream f ("apm.in");
    f>>N>>M;
    unsigned long i, x, y;
    short c;
    for(i=0; i<M; i++)
    {
        f>>x>>y>>c;
        push (x, y, c);
        push (y, x, c);
    }
}

void Graf::afisare()
{
    ofstream f ("apm.out");
    f<<cost<<'\n'<<N-1<<'\n';
    unsigned long i;
    for (i=2; i<=N; i++)
    {
        f<<i<<' '<<tati[i]<<'\n';
    }
}

int main()
{
    Graf G;
    G.citire();
    G.prim(1);
    G.afisare();
    return 0;
}