#include<stdio.h>
struct nod
{
    int vecin,cost;
    nod *adr;
};
nod *v[200001],*p;
void adaug(nod *&L,int v,int c)
{
    nod *p;
    p=new nod;
    p->vecin=v;
    p->cost=c;
    p->adr=L;
    L=p;
}
int N,M,i,x,y,c,k,vmin,s,d[200001],t[200001],viz[200001];
int main()
{
    freopen("apm.in","rt",stdin);
    freopen("apm.out","wt",stdout);
    scanf("%d %d",&N,&M);
    for(i=1;i<=N;i++)
    {
        v[i]=0;
    }
    for(i=1;i<=M;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        adaug(v[x],y,c);
        adaug(v[y],x,c);
    }
    for(i=1;i<=N;i++)
    {
        d[i]=1000000000;
        t[i]=0;
        viz[i]=0;
    }
    viz[1]=1;
    d[1]=0;
    for(p=v[1];p!=0;p=p->adr)
    {
        d[p->vecin]=p->cost;
        t[p->vecin]=1;
    }
    s=0;
    for(k=1;k<=N-1;k++)
    {
        vmin=1000000000;
        for(i=1;i<=N;i++)
        {
            if(viz[i]==0 && d[i]<vmin)
            {
                x=i;
                vmin=d[i];
            }
        }
        viz[x]=1;
        s=s+d[x];
        for(p=v[x];p!=0;p=p->adr)
        {
            if(d[p->vecin]>p->cost)
            {
                d[p->vecin]=p->cost;
                t[p->vecin]=x;
            }
        }
    }
    printf("%d\n",s);
    printf("%d\n",N-1);
    for(i=2;i<=N;i++)
    {
        printf("%d %d\n",t[i],i);
    }
    fclose(stdout);
    return 0;
}