#include <stdio.h>
#include <stdlib.h>
#define M 400001
#define N 200001
int muc[2*M],urm[2*M],back[2*M],id[2*M],vec[N],tata[N],n,m,vf;
int lg[N];
short int cost[2*M];
char viz[2*M];
void sort (int st,int dr)
{int s=st,d=dr,p=cost[id[st+rand()%(dr-st+1)]],aux;
 while(s<d)
 {while(cost[id[s]]<p)s++;
  while(cost[id[d]]>p)d--;
  if(s<=d)
  {aux=id[s];id[s]=id[d];id[d]=aux;
   s++;
   d--;
  }
 }
 if(s<dr)sort(s,dr);
 if(st<d)sort(st,d);
}
void adauga(int x,int y,int z)
{muc[vf]=y;
 back[vf]=x;
 cost[vf]=z;
 urm[vf]=vec[x];
 vec[x]=vf;
 vf++;
}

int main ()
{int i,x,y,z,p,q,S;
 freopen("apm.in","r",stdin);
 freopen("apm.out","w",stdout);
 scanf("%d %d",&n,&m);
 for (i=1,vf=1;i<=m;i++)
 {scanf("%d %d %d",&x,&y,&z);
  adauga(x,y,z);
  adauga(y,x,z);
 }
 for (i=1;i<=2*m;i++)id[i]=i;
 sort(1,2*m);
 for (i=1,S=0;i<=2*m;i++)
 {for(q=back[id[i]];tata[q];q=tata[q]);
  for(p=muc[id[i]];tata[p];p=tata[p]);
  if(p==q)continue;
  S+=cost[id[i]];
  viz[i]=1;
  if(lg[p]>lg[q])
  {tata[q]=p;
  }
  else if(lg[q]>lg[p])
  {tata[p]=q;}
  else
  {lg[p]++;
   tata[q]=p;
  }
 }
 printf("%d\n%d\n",S,n-1);
 for (i=1;i<=2*m;i++)
 {if(viz[i])
  printf("%d %d\n",back[id[i]],muc[id[i]]);
 }
 return 0;
}