#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct arc{
	int x;
	int y;
	int c;
} v[400001];
struct solutie{
	int xx;
	int yy;
} t[200001];
FILE*f=fopen("apm.in","r");
FILE*g=fopen("apm.out","w");
int nr,n,m,i,sol,w[200001];
int cmp(arc a, arc b) {
	return a.c<b.c;
}
void update(int a,int b){
	while(w[a]>0)
		a=w[a];

	while(w[b]>0)
		b=w[b];

	if(a!=b){
		sol+=v[i].c;
		if(a>b){
			w[b]+=w[a];
			w[a]=b;
		}else{
			w[a]+=w[b];
			w[b]=a;
		}
		t[++nr].xx=v[i].x;
		t[nr].yy=v[i].y;
	}
		
		
}
int main() {
	fscanf(f,"%d%d",&n,&m);
	
	for(i=1;i<=m;++i)
		fscanf(f,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
		
	sort(v+1,v+m+1,cmp);
	
	for(i=1;i<=n;++i)
		w[i]=-1;
	
	for(i=1;i<=m;++i){
		update(v[i].x,v[i].y);
		if(nr==n-1)
			break;
	}
	fprintf(g,"%d\n%d\n",sol,n-1);
	for(i=1;i<n;++i)
		fprintf(g,"%d %d\n",t[i].xx,t[i].yy);
	fclose(g);
	fclose(f);
	return 0;
}