#include <stdio.h>
long m,n,a[100],b[100],c[100],v[100],t[100],k,x,y,cost,i,j,l,rez[100];
int main()
{freopen("apm.in","r",stdin);freopen("apm.out","w",stdout);
 fscanf(stdin,"%ld%ld",&n,&m);
  for(i=1;i<=m;i++)
   {fscanf(stdin,"%ld%ld%ld",&x,&y,&c[i]);a[i]=x;b[i]=y;}
 for(i=1;i<=m;i++)for(j=i+1;j<=m;j++)
  if(c[i]>c[j])
   {x=a[i];a[i]=a[j];a[j]=x;
    x=b[i];b[i]=b[j];b[j]=x;
    x=c[i];c[i]=c[j];c[j]=x;}
 for(i=1;i<=m;i++)
  {if(!v[t[a[i]]]&&!v[t[b[i]]]){cost+=c[i];k++;v[a[i]]=k;t[a[i]]=a[i];t[b[i]]=a[i];l++;rez[l]=i;}
    else if(v[t[a[i]]]&&!v[t[b[i]]])
     {cost+=c[i];k++;t[b[i]]=t[a[i]];l++;rez[l]=i;}
     else if(!v[t[a[i]]]&&v[t[b[i]]])
      {cost+=c[i];k++;t[a[i]]=t[b[i]];l++;rez[l]=i;}
      else if(v[t[a[i]]]!=v[t[b[i]]])
       {cost+=c[i];if(v[t[a[i]]]<v[t[b[i]]])t[b[i]]=t[a[i]];else t[a[i]]=t[b[i]];l++;rez[l]=i;}
  }
 fprintf(stdout,"%ld\n%ld\n",cost,n-1);
 for(i=1;i<n;i++)fprintf(stdout,"%ld %ld\n",a[rez[i]],b[rez[i]]);
 fclose(stdin);fclose(stdout);
 return 0;
}