#include<stdio.h>

#define IN "apm.in"
#define OUT "apm.out"
#define maxn 4100

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");

int gr[maxn],x[maxn],y[maxn],c[maxn];
int n,m,ans,ind[maxn];
int vans[maxn];

int grupa(int);
void reuniune(int,int);
void quick(int,int);
int poz(int,int);

int main()
{
 int i;
    
 fscanf(fin,"%d %d\n",&n,&m);
 for(i=1;i<=m;i++)
 {
  fscanf(fin,"%d %d %d\n",&x[i],&y[i],&c[i]);
  ind[i]=i;
 }
 fclose(fin);

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

 quick(1,m);

 for(i=1;i<=m;i++)
 {
  if(grupa(x[ind[i]])!=grupa(y[ind[i]]))
  {
   ans=ans+c[ind[i]];
   reuniune(x[ind[i]],y[ind[i]]);
   vans[0]++;
   vans[vans[0]]=ind[i];
  }
 }

 fprintf(fout,"%d\n",ans);
 fprintf(fout,"%d\n",n-1);
 for(i=1;i<=n-1;i++)
  fprintf(fout,"%d %d\n",x[vans[i]],y[vans[i]]);
 fclose(fin);
  
 return 0;
}

int grupa(int i)
{
 if(gr[i]==i)
  return i;
  
 gr[i]=grupa(gr[i]);
 return gr[i];
}

void reuniune(int i,int j)
{
 gr[grupa(i)]=grupa(j); 
}

void quick(int st,int dr)
{
 if(st<dr)
 {
  int k=poz(st,dr);
  quick(st,k-1);
  quick(k+1,dr);
 }
}

int poz(int st,int dr)
{
 int i=st;
 int j=dr;
 int ii=0;
 int jj=-1;
 int aux;
 
 while(i<j)
 {
  if(c[i]>c[j])
  {
   aux=ind[i];
   ind[i]=ind[j];
   ind[j]=aux;

   aux=ii;
   ii=-jj;
   jj=-aux;
  }
  i=i+ii;
  j=j+jj;
 }
 return i;
}