#include<fstream.h>
#include<algorithm>
using namespace std;
struct muchie{
	int x,y,c,s;
}a[500001];
 int n,m,i,j,v[200001],k,r1,r2,ct;
 ifstream f("apm.in");
 ofstream g("apm.out");
 int cmp(muchie a, muchie b){
	 if(a.c<b.c)
	    return 1;
 return 0;
 }	 
		 int main ()
 {
 f>>n>>m;
 for(i=1;i<=m;i++)
	f>>a[i].x>>a[i].y>>a[i].c;
 sort(a+1,a+m+1,cmp);
 k=0;
 i=1;ct=0;
 for(i=1;i<=n;i++)
	v[i]=-1;
 i=1; 
 while(k<n-1)
     {
	  //gasim radacina arborelui din care face parte a[i].x
		r1=a[i].x;
		while(v[r1]>0)
			r1=v[r1];
		//gasim radacina arborelui din care face parte a[i].y
		r2=a[i].y;
		while(v[r2]>0)
			r2=v[r2];
		if(r1!=r2){
			ct+=a[i].c;
	 	    a[i].s=1;
			//unificam cei 2 arbori
			if(v[r2]>v[r1])
			  {v[r1]+=v[r2];
			  v[r2]=r1;}
			else
				{v[r2]+=v[r1];
			  v[r1]=r2;}
			k++;
            }
  i++;
 }
 

g<<ct<<'\n'<<n-1<<'\n';	
for(i=1;i<=m;i++)
	if(a[i].s==1)
		g<<a[i].x<<' '<<a[i].y<<'\n';
 return 0;
}