#include <stdio.h>

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

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

void quicksort(long st, long dr)
{
 long i,j,p;
 
 i=st; j=dr; p=u[(st+dr)/2].c;
 if (i>=j)
    return;
 while (i<=j)
  {
   while (u[i].c<p) ++i;
   while (u[j].c>p) --j;
   if (i<=j)
    {
     u[0]=u[i];
     u[i]=u[j];
     u[j]=u[0];
     ++i;
     --j;
    }
  }
  if (st<j) quicksort(st,j);
  if (dr>i) quicksort(i,dr);
}

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;
    quicksort(1,m);
    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;
}