#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream o("apm.out");
struct dat{
	int x,y,z;
};
int n,m;
dat a[400040];
int tt[200020],rg[200200],rs[200100];
bool funct(dat i,dat j){
	return i.z<j.z;
}
int find(int x){
	int r,y;
	for(r=x;tt[r]!=r;r=tt[r]);
	for(;tt[x]!=x;){
		y=tt[x];
		tt[x]=r;
		x=y;
	}
	return r;
}
void unit(int x,int y){
	x = find(x);
	y = find(y);
	if(rg[x]>rg[y])tt[y]=x;
	else tt[x]=y;
	if(rg[x]==rg[y])rg[y]++;
}
int main(){
f>>n>>m;
for(int i=1;i<=m;i++)rg[i]=1,tt[i]=i;
for(int i=1;i<=m;i++){
	f>>a[i].x>>a[i].y>>a[i].z;
}
sort(a+1,a+m+1,funct);
int j=0,sum=0;
for(int i=1;i<=m && j<n;i++){
	if(find(a[i].x)!=find(a[i].y)){
		unit(a[i].x,a[i].y);
		sum+=a[i].z;
		j++;
		rs[j]=i;
	}
}

o<<sum<<"\n";
o<<n-1<<"\n";
for(int i=1;i<n;i++)o<<a[rs[i]].x<<" "<<a[rs[i]].y<<"\n";

}