#include<stdio.h>
#define N 200010
#define M 400010
int n,m,i,j,a[M],b[M],c[M],d[N],ca[N],cb[N],la,lb,conexe(int aa,int bb);
void readd(),sort(),sw(int i1,int i2),hd(int ic,int nc),
kruskal(),conecteaza(int aa,int bb),prints();
int main()
{
	readd();
	sort();
	kruskal();
	prints();
	return 0;
}
void readd()
{
	freopen("apm.in","rt",stdin);
	freopen("apm.out","wt",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
}
void sort()
{
	for(i=m/2;i>=1;i--)hd(i,m);
	for(i=m;i>=1;i--){sw(1,i);hd(1,i-1);}
}
void sw(int i1,int i2)
{
	int aux=a[i1];a[i1]=a[i2];a[i2]=aux;
	    aux=b[i1];b[i1]=b[i2];b[i2]=aux;
	    aux=c[i1];c[i1]=c[i2];c[i2]=aux;
}
void hd(int ic,int nc)
{
	int is=ic<<1;
	if(is>nc)return;
	if(is<nc&&c[is]<c[is+1])is++;
	if(c[is]>c[ic]){sw(is,ic);hd(is,nc);}
}


void kruskal()
{
    for(i=1;i<=n;i++)d[i]=i;
    for(i=1,j=1;j<n;i++)
    { if(conexe(a[i],b[i]))continue;
      conecteaza(a[i],b[i]);
      a[j]=a[i];b[j]=b[i];c[j]=c[i];j++;
    }
}
void conecteaza(int aa,int bb)
{ int ia,ib;
  la=0;do{ ca[++la]=aa;aa=d[aa];}while(d[aa]-aa);ca[++la]=aa;
  lb=0;do{ cb[++lb]=bb;bb=d[bb];}while(d[bb]-bb);cb[++lb]=bb;
  aa=(aa<bb)?aa:bb;
  for(ia=1;ia<=la;ia++)d[ca[ia]]=aa;
  for(ib=1;ib<=lb;ib++)d[cb[ib]]=aa;
}
int conexe(int aa,int bb)
{ int ia,ib;
  la=0;do{ ca[++la]=aa;aa=d[aa];}while(d[aa]-aa);ca[++la]=aa;
  lb=0;do{ cb[++lb]=bb;bb=d[bb];}while(d[bb]-bb);cb[++lb]=bb;
  for(ia=1;ia<=la;ia++)d[ca[ia]]=aa;
  for(ib=1;ib<=lb;ib++)d[cb[ib]]=bb;
 if(aa==bb)return 1;return 0;
}
void prints()
{       int capm;
	for(i=1;i<n;i++)capm+=c[i];
	printf("%d\n",capm);
	n--;
	printf("%d\n",n);
	for(i=1;i<=n;i++)printf("%d %d\n",a[i],b[i]);
}