#include<stdio.h>
#include<algorithm>
using namespace std;

FILE*f=fopen("apm.in","r");
FILE*g=fopen("apm.out","w");

int N,M,i,Cost,sol[200005],T[200005],k;
int root(int nod){
	int nod2 = nod;
	while ( T[nod] > 0 )
		nod = T[nod];
	while ( T[nod2] > 0 ){
		T[nod2] = nod;
		nod2 = T[nod2];
	}
	return nod;
}

struct mch{
	int x;
	int y;
	int cst;
}W[400005];

int cmp(mch a,mch b){
	return a.cst < b.cst;
}

void reun(int nod1,int nod2){
	int ra = root(nod1);
	int rb = root(nod2);
	if ( T[ra] < T[rb] ){
		T[rb] = ra;
		T[ra] -= T[rb];
	}
	else{
		T[rb] += T[ra];
		T[ra] = rb;
	}
	
}

int main () {
	
	fscanf(f,"%d %d",&N,&M);
	
	for ( i = 1 ; i <= M ; ++i ){
		fscanf(f,"%d %d %d",&W[i].x,&W[i].y,&W[i].cst);
	}
	
	sort(W+1,W+M+1,cmp);
	
	for ( i = 1 ; i <= N ; ++i )
		T[i] = -1;
	
	for ( i = 1 ; i <= M && k < N - 1 ; ++i ){
		
		if ( root(W[i].x) != root(W[i].y) ){
			sol[++k] = i ;
			
			reun(W[i].x,W[i].y);
			//T[root(W[i].x)] = root(W[i].y);
			
			Cost += W[i].cst;
			
		}
		
		
	}
	
	fprintf(g,"%d\n%d\n",Cost,k);
	
	for ( i = 1 ; i <= k ; ++i ){
		fprintf(g,"%d %d\n",W[sol[i]].x,W[sol[i]].y);
	}
	
	
	fclose(f);
	fclose(g);
	
	return 0;
}