#include <iostream>
#include <fstream>

using namespace std;

class Graf
{
    unsigned long N, M;
    struct muchie {unsigned long nod1, nod2; short cost;};
    struct semi {unsigned long nod; short cost; semi *urm;};
    struct semimuchie {unsigned long nod; short cost;};
    long cost;
    //vector <muchie> toate;
    muchie A[400001];
    semi * G[200001];
    void push (unsigned long unde, unsigned long nod, short C);
public:
    Graf ();
    void citire();
    void prim (unsigned long r);
    void afisare ();
    ~Graf ();
};

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::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;
}

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

void Graf::prim(unsigned long r)
{
    semimuchie v[N+1]; //first-nodul din arbore de care se leaga nodul i; second-costul
    unsigned long i, x, k, minim;
    semi *j;
    short c;
    cost=0;
    muchie m;
    for (i=0; i<=N; i++)
    {
        v[i].cost=2000;
    }
    v[r].cost=-2000;//un nod are costul -2000 daca apartine arborelui
    v[r].nod=0;
    for (i=1; i<N; i++)
    {
        //in r avem ultimul nod ales
        for (j=G[r]; j!=NULL; j=j->urm)
        {
            x=j->nod;
            c=j->cost;
            if (c<v[x].cost && c!=-2000)
            {
                v[x].cost=c;
                v[x].nod=r;
            }
        }
        //am updatat vectorul
        minim=0;
        for (k=1; k<=N; k++)
        {
            if (v[k].cost<v[minim].cost && v[k].cost!=-2000)
            {
                minim=k;
            }
        }
        m.nod1=minim;
        m.nod2=v[minim].nod;
        m.cost=v[minim].cost;
        A[0].nod1++;
        A[A[0].nod1]=m;
        cost+=m.cost;
        v[minim].cost=-2000;
        r=minim;
    }
}

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=1; i<N; i++)
    {
        f<<A[i].nod1<<' '<<A[i].nod2<<'\n';
    }
}

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