#include<fstream.h>
#define endl '\n'
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{int x,y,c;};
typedef muchie* pm;
struct set{int p;};
set w[200001];
muchie v[400001],h[200001];
int cc[200001],m,n;
int fcmp(const void *a,const void *b){
	return ((pm)a)->c-((pm)b)->c;
}

void makeset(int x){
	w[x].p=x;
}
int find(int x){
	if(x==w[x].p) return x;
	else return find(w[x].p);
}
void join(int x,int y){
	int xr,yr;
	xr=find(x);
	yr=find(y);
	w[yr].p=w[xr].p;
}
int main(){
	int i,j,sc,min,max,xr,yr;
	fin>>n>>m;
	for(i=0;i<m;i++) fin>>v[i].x>>v[i].y>>v[i].c;
	qsort(v,m,sizeof(v[0]),fcmp);
	for(i=1;i<=n;i++) {
		cc[i]=i;
		makeset(i);
	}
	int ma=1;
	i=0;
	sc=v[0].c;
	h[0]=v[0];
	if(cc[v[0].x]<cc[v[0].y]) cc[v[0].y]=cc[v[0].x];
	else cc[v[0].x]=cc[v[0].y];
	join(v[i].x,v[i].y);
	while(ma<n-1){
		do{
			i++;
		}while(cc[v[i].x]==cc[v[i].y]);
		h[ma]=v[i];
		ma++;
		sc+=v[i].c;
		if(cc[v[i].x]<cc[v[i].y]) min=cc[v[i].x],max=cc[v[i].y];
		else min=cc[v[i].y],max=cc[v[i].x];
		xr=find(min);
		yr=find(max);
		/*for(j=1;j<=n;j++) 
			if(cc[j]==max) cc[j]=min;
	*/
		join(xr,yr);
	}
	fout<<sc<<endl;
	fout<<n-1<<endl;
	for(i=0;i<n-1;i++)
		fout<<h[i].x<<" "<<h[i].y<<endl;
	return 0;
}