#include<fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{
	int x,y;
	float c;
};
muchie v[100];
int n,k;
void citire(){
	int i;
	f>>n>>k;
	for(i=1;i<=k;++i)
		f>>v[i].x>>v[i].y>>v[i].c;
}
void sortare(){
	int i,j;
	muchie aux;
	for(i=1;i<k;++i)
		for(j=i+1;j<=k;++j)
			if(v[i].c>v[j].c){
				aux=v[i];
				v[i]=v[j];
				v[j]=aux;
			}
}
void closhcar(){
	int a[100],i,w,t=0;
	float s=0;
	for(i=1;i<=n;++i)
		a[i]=i;
	w=1;
	while(t<n-1){
		if(a[v[w].x]!=a[v[w].y]){
			t++;
			for(i=1;i<=n;++i)
				if(a[i]==a[v[w].x])
					a[i]=a[v[w].y];
			//g<<v[w].x<<' '<<v[w].y<<'\n'; 
			s+=v[w].c;	
		}
		else v[w].x=v[w].y;
		w++;
	}
	g<<s<<'\n'<<n-1<<'\n'; t=0;
	for(i=1;i<=k&&t<n-1;++i)
		if(v[i].x!=v[i].y){
			g<<v[i].x<<' '<<v[i].y<<'\n';
			t++;
		}
}
int main(){
	citire();
	sortare();
	closhcar();
	g.close();
	return 0;
}