#include<fstream.h>

ofstream fout("apm.out");

int m1[400000],t[400000],h[400000];
long long int p,n,m,k=1,nr;
struct nod { int a,b;
	     long long int c;
	   };
nod a[400000];

void citire()
{       ifstream fin("apm.in");
	fin>>n>>m;
	for(int i=1;i<=m;i++)
		fin>>a[i].a>>a[i].b>>a[i].c;
	fin.close();
}

void quick(long long int x,long long int y)
{    long long int i,j,p=0;
     nod aux;
     if(x<y)
     {	i=x-1;
	j=y+1;
	p=a[(x+y)/2].c;
	while(i<j)
	{   do i++; while(a[i].c<p);
	    do j--; while(a[j].c>p);
	    if(i<j) {  aux=a[i];
		       a[i]=a[j];
		       a[j]=aux;
		    }
	}
	quick(x,i-1);
	quick(j+1,y);
     }
}

int arb(int no)
{   while(t[no]) no=t[no];
    return no;
}

int main()
{	citire();
	quick(1,m);
	k=1;
	do {  while(arb(a[k].a)==arb(a[k].b)) k++;
	      nr++;
	      p+=a[k].c;
	      m1[k]=1;
	      if(h[a[k].a]==h[a[k].b])
	      {	t[a[k].a]=a[k].b;
		h[a[k].a]++;
	      }
	      else if(h[a[k].a]<h[a[k].b])
			t[a[k].a]=a[k].b;
		   else t[a[k].b]=a[k].a;
	      k++;
	   }while(nr<n-1);
	fout<<p<<"\n"<<nr<<"\n";
	for(int i=1;i<=m;i++)
	    if(m1[i]==1) fout<<a[i].a<<" "<<a[i].b<<"\n";
	fout.close();
	return 0;
}