# include <cstdio>
# include <algorithm>
using namespace std;

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

long n,m,k,i,ct,l[200005],j,nr1,nr2;
int cmp(muchie x, muchie y )
{
    return x.c<y.c;
}

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;
        }
   sort(u+1,u+m+1,cmp);

//   for(i=1;i<=m;i++)
//    printf("%ld %ld %ld\n", u[i].x, u[i].y, u[i].c);

   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;
}