#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];
void quick(int st,int dr)
{int s=st,d=dr,p=c[idx[rand()%(dr-st+1)+st]],aux;
 while(s<=d)
 {while(c[idx[s]]<p)s++;
  while(c[idx[d]]>p)d--;
  if(c[idx[s]]>=c[idx[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);
  //
  viz[idx[j-1]]=1;
  tata[a]=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;
}