#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f1=fopen("apm.in","r");
FILE *f2=fopen("apm.out","w");
int n,m,i,j,v[200001],cost,nrsol,sol[400001][2];
struct muchie{
   int n1,n2,c;
}muchii[400001];
int comp(muchie a,muchie b){
     if (a.c<b.c) return 1;
     return 0;
}
int arb(int x){
    while(v[x]!=x) x=v[x];
    return x;
}
void unif(int a,int b){
     v[arb(a)]=arb(b);
}
int main(){
    fscanf(f1,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
        fscanf(f1,"%d%d%d",&muchii[i].n1,&muchii[i].n2,&muchii[i].c);
    fclose(f1);
    sort(muchii+1,muchii+m+1,comp);
    for (i=1;i<=n;i++)
        v[i]=i;
    for (i=1;i<=m;i++)
      if (arb(muchii[i].n1)!=arb(muchii[i].n2))
        {
            nrsol++;
            sol[nrsol][1]=muchii[i].n1;
            sol[nrsol][2]=muchii[i].n2;
            cost=cost+muchii[i].c;
            unif(muchii[i].n1,muchii[i].n2);
            if (nrsol==n-1)
                {
                    fprintf(f2,"%d\n%d\n",cost,nrsol);
                    for (j=1;j<=nrsol;j++)
                        fprintf(f2,"%d %d\n",sol[j][1],sol[j][2]);
                    fclose(f2);
                    return 0;
                }
        }
    fclose(f2);
    return 0;
}