#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");
int n,m,i,t[200001],k,r1,r2,cmin;
struct nod{
	int a;
	int b;
	int c;
} v[400001];
bool s[400001];
int cmp(const void *lhs,const void *rhs)
{
	const nod *a = (const nod *) lhs;
	const nod *b = (const nod *) rhs;
	
	if (a->c > b->c)
		return 1;
	else if (a->c == b->c)
		return 0;
	else
		return -1;
	
   //return return ( *(int*)lhs - *(int*)rhs);	
}
int main(){
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++)
		 fscanf(f,"%d%d%d",&v[i].a,&v[i].b,&v[i].c);
for(i=1;i<=n;i++)
	t[i]=-1;
qsort(v+1, m, sizeof (nod), cmp);	
k=0; i=1;

while(k < n-1){
    if(t[v[i].a] < 0)
		  r1=v[i].a;
	else
	r1=t[v[i].a];
	if(t[v[i].a] < 0)
		  r1=v[i].a;
	else
	r2=t[v[i].b];
	while(r1>0){
		r1=t[r1];
	}
	while(r2>0){
		r2=t[r2];
	}
	if(r1!=r2){
		  if(t[r1] < t[r2] ){
			    t[r1]-=t[r2];
				t[r2]=r1;
		  }
		else { t[r2]-=t[r1];
			   t[r1]=r2;
		}
	k++;
	cmin+=v[i].c;
//	mu.push_back(i);
    s[i]=1;	
	}
i++;
}
fprintf(g,"%d\n%d\n",cmin,n-1);/*
for(i=0;i<=mu.size()-1;i++)
	fprintf(g,"%d %d\n",v[mu[i]].a,v[mu[i]].b);*/
for(i=1;i<=n;i++)
	if(s[i])
		fprintf(g,"%d %d\n",v[i].a,v[i].b);
	
return 0;	
}