#include<stdio.h>
#include<algorithm>
using namespace std;

struct muchii {int a,b,c;} v[400011];
int t1,t2,n,m,M,i,s,t[200011];
char c[400011];

int tata(int x){
   while(t[x] > 0){
   x=t[x];
   }

return x;
}

int cmp(muchii a, muchii b){
return a.c < b.c;
}

int main(){

FILE *f=fopen("apm.in","r");
fscanf(f,"%d %d",&n,&m);
   for(i=1;i<=m;i++)
   fscanf(f,"%d %d %d",&v[i].a,&v[i].b,&v[i].c);
fclose(f);

sort(v+1,v+1+m,cmp);

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

   for(i=1;i<=m && M!=n-1 ;i++){
   t1=tata(v[i].a);
   t2=tata(v[i].b);
   
     if(t1!=t2){
     s+=v[i].c;
       if( -t[t1] < -t[t2]){
       t[t2]+=t[t1];
       t[t1]=t2;
       }

       else{
       t[t1]+=t[t2];
       t[t2]=t1;
       }

     c[i]=1;
     M++;
     }
     
   }

FILE *g=fopen("apm.out","w");
fprintf(g,"%d\n%d\n",s,n-1);

   for(i=1;i<=m;i++)
     if(c[i])
     fprintf(g,"%d %d\n",v[i].a,v[i].b);
     
fclose(g);

return 0;
}