#include <cstdio>
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");

int n,i,sw,k,j,cost,m;
int l[200001];

struct nod_graf
{
    int ei,ef,c;
}v[400001],aux;

struct nod
{
    int ei,ef;
    nod *urm;
}*p,*prim,*ultim;


int main()
{
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
        fscanf(f,"%d %d %d",&v[i].ei,&v[i].ef,&v[i].c);


    do
    {
        sw=0;
        for(i=1;i<m;i++)
            if(v[i].c>v[i+1].c)
            {
                aux=v[i];
                v[i]=v[i+1];
                v[i+1]=aux;
                sw=1;
            }
            else
                if(v[i].c==v[i+1].c)
                    if(v[i].ei>v[i+1].ei)
                    {
                        aux=v[i];
                        v[i]=v[i+1];
                        v[i+1]=aux;
                        sw=1;
                    }
                    else
                        if(v[i].ei==v[i].ei)
                            if(v[i].ef>v[i].ef)
                            {
                                aux=v[i];
                                v[i]=v[i+1];
                                v[i+1]=aux;
                                sw=1;
                            }
    }
    while(sw==1);

    for(i=1;i<=n;i++)
        l[i]=i;

    k=1;
    cost=0;
    i=1;

    while(k<n)
    {
        if(l[v[i].ei]!=l[v[i].ef])
        {
            p=new nod;
            p->ei=v[i].ei;
            p->ef=v[i].ef;
            if(prim==NULL)
                prim=ultim=p;
            else
            {
                ultim->urm=p;
                ultim=p;
            }
            k++;
            cost+=v[i].c;
            for(j=1;j<=n;j++)
                if(l[j]==l[v[i].ei])
                    l[j]=l[v[i].ef];
        }
        i++;
    }

    ultim->urm=NULL;
    k--;
    fprintf(g,"%d\n%d\n",cost,k);

    p=prim;
    for(i=1;i<=k;i++)
    {
        fprintf(g,"%d %d\n",p->ei,p->ef);
        p=p->urm;
    }


    fclose(f);
    fclose(g);

    return 0;
}