#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define maxn 200005
#define maxm 400005

int x[maxm],y[maxm],c[maxm],indice[maxm];
int tata[maxn],*a;
int n,m,cost;

    void citire(void)
    {   FILE *fin=fopen("apm.in","r");
        fscanf(fin,"%d%d",&n,&m);
        for(int k=0;k<m;k++)
        {
            fscanf(fin,"%d%d%d",&x[k],&y[k],&c[k]);
            indice[k]=k;
        }
        fclose(fin);
    }

    int gaseste(int x)
    {   int r=x;
        while(tata[r]!=r) r=tata[r];
        int y=x;
        while(y!=r)
        {   int t=tata[y];
            tata[y]=r;
            y=t;
        }
        return r;
    }

    void unire(int x,int y)
    {
        tata[x]=y;
    }

    int compara(const void *i,const void *j)
    {
        return ( c[*(int*)i]-c[*(int*)j] );
    }

    void kruskal(void)
    {   int k,i,j;
        for(k=1;k<=n;k++) tata[k]=k;
        qsort(indice,m,sizeof(int),compara);
        a=(int*)realloc(a,sizeof(int));
        a[0]=0;
        for(k=0;k<m;k++)
        {   i=gaseste(x[ indice[k] ]);
            j=gaseste(y[ indice[k] ]);
            if(i!=j)
            {   a[0]++;
                a=(int*)realloc(a, (a[0]+1)*sizeof(int));
                a[a[0]]=indice[k];
                cost+=c[indice[k]];
                unire(i,j);
            }
        }
    }

    void afisare(void)
    {   FILE *fout=fopen("apm.out","w");
        fprintf(fout,"%d\n%d\n",cost,a[0]);
        for(int k=1;k<=a[0];k++) fprintf(fout,"%d %d\n",x[a[k]],y[a[k]]);
        fclose(fout);
    }

int main(void)
{   citire();
    kruskal();
    afisare();
    return 0;
}