#include<stdio.h>
long n,m,c[200000],a[400000];
long long costul;
 
struct muchie
    {
    long e1,e2;
    int cost;
    } g[400000],aux;
 
void read ()
    {
    FILE *f=fopen("apm.in","r");
    fscanf(f,"%ld%ld",&n,&m);
    long i;
    for (i=1;i<=m;++i)
        fscanf(f,"%ld%ld%d",&g[i].e1,&g[i].e2,&g[i].cost);
    fclose(f);
    }
 
void quick (int s, int d)
    {
    int m=(s+d)/2,i=s,j=d,x;
    x=g[m].cost;
    while (i<=j)
        {
        while (g[i].cost<x)
            i++;
        while (x<g[j].cost)
            --j;
        if (i<=j)
           {
            aux=g[i];
            g[i]=g[j];
            g[j]=aux;
            i++;
            j--;
            }
        }
    if (s<j)
        quick(s,j);
    if (i<d)
        quick(i,d);
    }
 
void init ()
    {
    long i;
    for (i=1;i<=n;++i)
        c[i]=i;
    }
 
void solve ()
    {
    long i,j,nr=0,min,max;
    for (i=1; nr<n-1; ++i)
        if (c[g[i].e1]!=c[g[i].e2])
            {
            a[++nr]=i;
            costul+=g[i].cost;
            if (c[g[i].e1]<c[g[i].e2])
                {
                min=c[g[i].e1];
                max=c[g[i].e2];
                }
            else
                {
                min=c[g[i].e2];
                max=c[g[i].e1];
                }
            for (j=1;j<=n;++j)
                if (c[j]==max)
                    c[j]=min;
            }
    }
 
void write ()
    {
    FILE *f=fopen("apm.out","w");
    fprintf(f,"%lld\n%ld\n",costul,n-1);
    long i;
    for (i=1;i<=n-1;++i)
        fprintf(f,"%ld %ld\n",g[a[i]].e1,g[a[i]].e2);
    fclose(f);
    }
 
int main ()
{
read ();
quick (1,m);
init ();
solve ();
write ();
return 0;
}