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