#include <stdio.h>

struct muchie{
              long x,y,c;
             }u[200005],sol[200005];

long n,m,k,i,ct,l[200005],j,nr1,nr2;


int main()
{
   freopen("apm.in","r",stdin);
   freopen("apm.out","w",stdout);
   scanf("%ld %ld", &n, &m);
   for (i=1;i<=m;++i)
        {
        scanf("%ld %ld %ld", &u[i].x, &u[i].y, &u[i].c);
        l[i]=i;
        }
    
   for(i=1;i<m;i++)
    for(j=i+1;j<=m;j++)
      if (u[i].c >= u[j].c)
       {
       u[0]=u[i];
       u[i]=u[j];
       u[j]=u[0];
       }
    
   i=1;
   while (k<n-1)
        {
         if (l[u[i].x]!=l[u[i].y])
            {
             ++k;
             ct+=u[i].c;
             sol[k]=u[i];
             nr1=l[u[i].x]; nr2=l[u[i].y];
             for (j=1;j<=n;++j)
                 if (l[j]==nr2) l[j]=nr1;
            }
         ++i;
        }
  printf("%ld\n%ld\n", ct, k);
  for (i=1;i<=k;++i)
      printf("%ld %ld\n", sol[i].x, sol[i].y);
  return 0;
}