#include<fstream>
#include<bitset>
#include<algorithm>
#define dim 400022
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
bitset<dim>ok;
int T[dim],n,m,i,a,b,k,suma;
int tata(int x){
	if(T[x]>0)
		return tata(T[x]);
	return 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;
			++k;
			ok[i]=1;
		}
	}
	
	g<<suma<<"\n";
	g<<k<<"\n";
	for(i=1;i<=n;i++)
		if(ok[i]==1)
			g<<v[i].x<<" "<<v[i].y<<"\n";		
	
	return 0;
}