#include <iostream>
#include <fstream>

using namespace std;

struct nod
{
    int info, cost;
    nod *next;
};

ifstream f("apm.in");
ofstream g("apm.out");
nod * L[200001];
int n, m, ctotal, pinf=1001;
int s[200001], t[200001];

void read()
{
    f>>n>>m;
    int i,x,y,c;
    nod* q;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        ///adaug y in lista lui x
        q=new nod;
        q->info=y;
        q->cost=c;
        q->next=L[x];
        L[x]=q;
        ///adaug x in lista lui y
        q=new nod;
        q->info=x;
        q->cost=c;
        q->next=L[y];
        L[y]=q;

    }
}

int minim(int &a)
{
    nod * q;
    int x=pinf, i, ok;
    for(i=1; i<=n; i++)
        if(s[i]!=0)
        {
            q=L[i];
            ok=0;
            while(ok==0 && q!=0)
            {
                if(q->info==s[i])
                {
                    if(q->cost<x)
                    {
                        x=q->cost;
                        a=i;
                    }
                    ok=1;
                }
                q=q->next;
            }
        }

    return x;
}
void update(int nodc)
{
    int i, costi, costp, ok;
    nod *q;
    for(i=1; i<=n; i++)
        if(s[i]!=0)
        {
            ok=0;
            costi=pinf;
            costp=pinf;
            q=L[i];
            while(ok<2 && q!=0)
            {
                if(q->info==s[i])
                {
                    costi=q->cost;
                    ok++;
                }
                if(q->info==nodc)
                {
                    costp=q->cost;
                    ok++;
                }

                q=q->next;
            }
            if(costp<costi)
                s[i]=nodc;
        }
}
void arbore(int root)
{
    int i,lowcost,nodc;
    for(i=1; i<=n; i++)
        if(i!=root)
            s[i]=root;
    for(i=1; i<=n-1; i++)
    {
        lowcost=minim(nodc);
        ctotal+=lowcost;
        t[nodc]=s[nodc];
        s[nodc]=0;
        update(nodc);
    }

}

int main()
{
    read();
    arbore(1);
    g<<ctotal<<'\n';
    g<<n-1<<'\n';
    int i;
    for(i=2;i<=n;i++)
    {
        g<<i<<" "<<t[i]<<'\n';
    }
    return 0;
}