#include<fstream>
#include<algorithm>
#define dim 400022
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int T[dim],n,m,i,a,b,k,suma,nr[dim];
int tata(int x){
	if(T[x]<0)
		return x;
	else
		return tata(T[x]);
}
struct muchii{
	int x,y,c;
};
muchii v[dim];
struct  cmp{
	bool operator ()(const muchii a,const muchii b)const{
		return a.c<b.c;
	}
	
};
int main (){
	f>>n>>m;
	for(i=1;i<=m;i++)
		f>>v[i].x>>v[i].y>>v[i].c;
	
	sort(v+1,v+m+1,cmp());
	
	for(i=1;i<=n;i++)
		T[i]=-1;
	for(i=1;i<=m;i++){
		a=tata(v[i].x);
		b=tata(v[i].y);
		if(a!=b){
			T[a]=T[a]+T[b];
			T[b]=a;
			suma+=v[i].c;
			nr[++k]=i;
		}
	}
	
	g<<suma<<"\n";
	g<<k<<"\n";
	for(i=1;i<=k;i++){
		g<<v[nr[i]].x<<" "<<v[nr[i]].y<<"\n";		
		
	}
	
	return 0;
}