#include<stdio.h>
#define dim 400001
#define dim2 200001
//#define minim(k,kk) (k)<(kk)?(k):(kk)
//#define maxim(k,kk) (k)>(kk)?(k):(kk)

int comp[dim2];
struct muchii
{
int x;
int y;
int c;
};

muchii m[dim],man[dim];
int v[dim];

int n,mm,nn,min,max,sum,n2;

void merge_sort(int li, int ls)
{
 int jum,i,j,k;

 jum=(li+ls)/2;

 if(li==ls) return;

 merge_sort(li,jum);
 merge_sort(jum+1,ls);

 i=li;
 j=jum+1;
 k=li;

 while( (i<=jum) || (j<=ls) )
  {
   if( j>ls || ( (i<=jum) && (m[i].c<m[j].c) ) )
     {
      man[k]=m[i];

      ++i;
      ++k;
     }
     else
      {
       man[k]=m[j];

       ++j;
       ++k;
      }
  }

 for(i=li;i<=ls;++i)
  m[i]=man[i];
}

int main()
{
 int i,j;

 freopen("apm.in","r",stdin);
 freopen("apm.out","w",stdout);

 scanf("%d %d", &n, &mm);

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

 for(i=1;i<=mm;++i)
   scanf("%d %d %d", &m[i].x, &m[i].y, &m[i].c);

 merge_sort(1,mm);

 nn=0;
 i=1;
 n2=n-1;
 while(nn<n2)
  {
   if(comp[m[i].x]!=comp[m[i].y])
    {
     if(comp[m[i].y]>comp[m[i].x])
       {
	    min=comp[m[i].x];
	    max=comp[m[i].y];
       }
       else
	    {
	     min=comp[m[i].x];
	     max=comp[m[i].y];
	    }
     //min=minim(comp[m[i].x],comp[m[i].y]);
     //max=maxim(comp[m[i].x],comp[m[i].y]);
     for(j=1;j<=n;j++)
      if(comp[j]==max)
       comp[j]=min;

     sum+=m[i].c;
     v[i]=1;
     ++nn;
    }
   ++i;
  }

 printf("%d \n", sum);
 printf("%d \n", n2);

 for(i=1;i<=mm;++i)
  if(v[i])
   printf("%d %d \n", m[i].x, m[i].y);
   
 return 0;
}