#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; 
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");
int n,m,arb[400002];

struct muchii{
	int i,j,c;
};
muchii v[400002];
int a[400002];


int cmp(muchii a,muchii b){
	if(a.c>b.c)
		return 0;
	return 1;
}

int radacina(int x){
	register int i,j;
	while(arb[x]>0){
		x=arb[x];
	}
	return x;
}

int main(void){
	register int i,j,k=0,cost=0;

	fscanf(f,"%d %d\n",&n,&m);
	memset(arb,-1,sizeof(arb));
	for(i=1;i<=m;i++)
		fscanf(f,"%d %d %d",&v[i].i,&v[i].j,&v[i].c);
	sort(v+1,v+m+1,cmp);
	
	for(i=1;i<=m;i++){
		int r1=radacina(v[i].i);
		int r2=radacina(v[i].j);
		if(r1!=r2){
			a[++k]=i;
			cost+=v[i].c;
			if(arb[r1]<arb[r2]){
				arb[r1]+=arb[r2];
				arb[r2]=r1;
			}
			else{
				arb[r2]+=arb[r1];
				arb[r1]=r2;
			}
		}
	}
	
	fprintf(g,"%d\n%d\n",cost,k);
	for(i=1;i<=k;i++)
		fprintf(g,"%d %d\n",v[a[i]].i,v[a[i]].j);
	fclose(f);
	fclose(g);
	return 0;
}