#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],t1,t2,h[200001];
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]!=0) x=v[x];
    return x;
}
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);
    j=0;
    for (i=1;i<n;i++){
      t1=0;t2=0;
      while(t1==t2){
        j++;
        t1=arb(muchii[j].n1);
        t2=arb(muchii[j].n2);
      }
      nrsol++;
      sol[nrsol][1]=muchii[j].n1;
      sol[nrsol][2]=muchii[j].n2;
      cost=cost+muchii[j].c;
      if (h[t1]>h[t2]){
        v[t2]=t1;
      }
        else
         if (h[t1]<h[t2]){
            v[t1]=t2;
        }
          else
            {
                v[t1]=t2;
                h[t2]++;
            }
    }
    fprintf(f2,"%d\n%d\n",cost,nrsol);
    for (i=1;i<=nrsol;i++)
        fprintf(f2,"%d %d\n",sol[i][1],sol[i][2]);
    fclose(f2);
    return 0;
}