#include<fstream.h>
#define endl '\n'
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{int x,y,c;};
typedef muchie* pm;
struct nod{int nr;nod *next;};
struct lista{nod *vf,*sf;};
muchie v[400001],h[200001];
lista w[200001];
int cc[200001],m,n;
void add(lista &l,int x){
	nod *n=new nod;
	n->nr=x;
	n->next=NULL;
	if(!l.vf) l.vf=n;
	else l.sf->next=n;
	l.sf=n;
}
int fcmp(const void *a,const void *b){
	return ((pm)a)->c-((pm)b)->c;
}
int main(){
	int i,j,sc,min,max;
	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;
	/*
	for(i=0;i<m;i++){
		add(w[v[i].x],v[i].y);
		add(w[v[i].y],v[i].x);
	}*/
	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];
	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];
		for(j=1;j<=n;j++) 
			if(cc[j]==max) cc[j]=min;
	}
	fout<<sc<<endl;
	fout<<n-1<<endl;
	for(i=0;i<n-1;i++)
		fout<<h[i].x<<" "<<h[i].y<<endl;
	return 0;
}