#include <fstream>

using namespace std;

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

struct nod {
    nod *next;
    int inf;
    int cost;
};

struct muchie {
    muchie *next;
    int a;
    int b;
    int cost;
};

nod *graf[100];
muchie *muchii,*mprim;
int viz[100],total,nr;

void citire ( int  , int  );
void adaugm ( int  , int  , int );
void prim ( int , int );
void adaugavecini ( int );
void adaugamuchia ( int, int, int );
void admprim ( int, int, int );
void scoatem (int );

using namespace std;

int main()
{
    int n,m;
    fin>>n>>m;
    citire (n,m);
    prim (1,n);
    fout<<total<<"\n";
    fout<<n-1<<"\n";
    while (mprim)
    {
        fout<<mprim->a<<" "<<mprim->b<<"\n";
        mprim=mprim->next;
    }
    return 0;
}

void citire ( int n , int m )
{
    int i,a,b,c;
    for ( i=1;i<=m;i++ )
    {
        fin>>a>>b>>c;
        adaugm (a,b,c);
    }

}


void adaugm (int a , int b, int c)
{
    nod *x;
    x=new nod();
    x->inf=b;
    x->cost=c;
    x->next=graf[a];
    graf[a]=x;
    x=new nod ();
    x->inf=a;
    x->cost=c;
    x->next=graf[b];
    graf[b]=x;
}

void prim ( int k , int n)
{
    nod *x;
    int j=0;
    x=new nod ();
    x=graf[k];
    viz[k]=1;
    adaugavecini (k);
    while (j<n-1)
    // while (muchii)
    {
        muchie *m;
        m=muchii;
        muchii=muchii->next;
        total+=m->cost;
        admprim(m->a,m->b,m->cost);
        adaugavecini(m->b);
        scoatem(m->b);

        j++;
    }


}

void scoatem ( int b)
{
    muchie *n,*m;
    m=new muchie();
    m=muchii->next;
    n=muchii;

    while (m)
    {
        if (viz[m->b]&&viz[m->a])
        {
            n->next=m->next;
            delete m;

            m=n->next;
        }
        else
        {
            m=m->next;
            n=n->next;
        }
    }
    if (viz[n->b]==1&& viz[n->a]==1)
        delete n;
    if (viz[muchii->b]==1&& viz[muchii->a]==1)
    {
        n=muchii;
        muchii=muchii->next;
        delete n;
    }
}

void admprim (int a , int b , int c )
{
    viz[b]=1;
    if (!mprim)
    {
        mprim=new muchie ();
        mprim->a=a;
        mprim->b=b;
        mprim->cost=c;
        mprim->next=NULL;

    }
    else
    {
        muchie *aux;
        aux=new muchie();
        aux->a=a;
        aux->b=b;
        aux->cost=c;
        aux->next=mprim;
        mprim=aux;

    }
}
void adaugavecini ( int k )
{
    nod *x;
    x=new nod ();
    x=graf[k];
    if (x->inf)
        while (x)
        {
            if (!viz[x->inf])
            {
                adaugamuchia(k,x->inf,x->cost);
                //viz[x->inf]=1;
            }
            x=x->next;
        }
}

void adaugamuchia ( int a , int b , int c )
{
    muchie *m;
    if (!muchii)
    {
        muchii=new muchie();
        muchii->a=a;
        muchii->b=b;
        muchii->cost=c;
        muchii->next=NULL;
    }
    else
    {
        if (c<muchii->cost)
        {
            m=new muchie();
            m->next=muchii;
            m->a=a;
            m->b=b;
            m->cost=c;
            muchii=m;
        }
        else
        {
            m=new muchie();
            m=muchii;
            while (m->next&&c>m->next->cost )
                m=m->next;
            if (m->next)
            {
                muchie *aux;
                aux=new muchie ();
                aux->next=m->next;
                m->next=aux;
                aux->a=a;
                aux->b=b;
                aux->cost=c;
            }
            else
            {
                muchie *aux;
                aux=new muchie ();
                m->next=aux;
                aux->a=a;
                aux->b=b;
                aux->cost=c;
                aux->next=NULL;
            }
        }
    }
}