#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])
     {
      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;

}