#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;
     i++;
     nn++;
    }
    else 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;
}