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

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

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

int main()
{
   freopen("apm.in","r",stdin);
   freopen("apm.out","w",stdout);
   scanf("%d %d", &n, &m);

   for (i=1;i<=m;++i)
    {
        scanf("%d %d %d", &u[i].x, &u[i].y, &u[i].c);
        l[i]=i;
    }

   //sortam crescator dupa cost
   sort(u+1,u+m+1,cmp);

   i=1;
   while (k<n-1)
    {
         if (l[u[i].x]!=l[u[i].y])
            {
             ++k;
             ct+=u[i].c;
             sol[k]=u[i];
             //unificam
             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("%d\n%d\n", ct, k);
  for (i=1;i<=k;++i)
      printf("%d %d\n", sol[i].x, sol[i].y);
  return 0;
}