#include <stdlib.h>
#include <stdio.h>
#define M 400001
#define N 200001
int x[M],y[M],c[M],n,m,idx[M],tata[N],viz[N],h[N];
void quick(int st,int dr)
{int s=st,d=dr,p=c[idx[st+rand()%(dr-st+1)]],aux;
 while(s<d)
 {while(c[idx[s]]<p)s++;
  while(c[idx[d]]>p)d--;
  if(s<=d)
  {aux=idx[s];idx[s]=idx[d]; idx[d]=aux;
   s++;
   d--;
  }
 }
 if(s<dr)quick(s,dr);
 if(st<d)quick(st,d);
}
int main ()
{int i,j,a,b,cost;
 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",&x[i],&y[i],&c[i]);
 for (i=1;i<=m;i++)idx[i]=i;
 quick(1,m);

 for (i=1,j=1,cost=0;i<n;i++)
 {if(a!=0&&b!=0)
  {do
   {for (a=x[idx[j]];tata[a];a=tata[a]);
    for (b=y[idx[j]];tata[b];b=tata[b]);
    j++;
   }
   while(a==b);
  }
  else j++;
  viz[idx[j-1]]=1;
  if(h[a]>h[b])
  {tata[b]=a;
  }
  else if(h[b]>h[a])
  {tata[a]=b;
  }
  else
  {tata[a]=b;
   h[b]++;
  }
  cost+=c[idx[j-1]];
 }
 printf("%d\n%d\n",cost,n-1);
 for (i=1;i<=m;i++)
 {if(viz[i]==1)
  {printf("%d %d\n",x[i],y[i]);
  }
 }
 i=i;
 return 0;
}