#include <stdio.h>
int n,m, L[10000],a[10000],b[10000];
struct muchie{ int x,y,c;}; muchie u[10000];
void init()
{ int i;
for(i=1;i<=n;i++)
L[i]=i;
}
void citire()
{
int i,x,y,c;
 freopen("apm.in", "r", stdin);
 freopen("apm.out", "w", stdout);
   scanf("%d %d",  &n, &m);
  while(scanf("%d %d %d",x, y, c))
   { u[i].x=x;
     u[i].y=y;
     u[i].c=c;
   }
m=i;
}
void sortare()
{ int j,i;  muchie aux;
  for(i=1;i<m;i++)
 for(j=i+1;j<=m;j++)
  if(u[i].c>u[j].c)
    {
     aux=u[i];
     u[i]=u[j];
     u[j]=aux;
    }
}
int main ()
{
 int i=1,j,k=0,ct=0,x,y;
citire();
sortare();
init();
 while(k<n-1)
{
if(L[u[i].x]!=L[u[i].y])
{
 k++;
 ct=ct+u[i].c;
  a[k]=u[i].x;
  b[k]=u[i].y;
  x=L[u[i].y];
 y=L[u[i].x];
for(j=1;j<=n;j++)
 if(L[j]==x)
 L[j]=y;
}
i++;
}
printf("%d",ct);
printf("%d",n-1);
 for(i=1;i<=n-1;i++)
   printf("%d %d", a[i],b[i]);
return 0;
}