#include <fstream>
#include <algorithm>
#include <stdio.h>

#define N 200000

using namespace std;

int E1[2*N], E2[2*N], EC[2*N], Ei[2*N], ES[N], NP[N+1], n, m, i, msel=0, a, b;
long long sum=0;
FILE *fpi = fopen("apm.in", "r");
ofstream fpo("apm.out");

bool compara(int a, int b){
	return EC[a]<EC[b];
}

int gaseste(int i){
	int rad, z;
	for(rad=i; rad!=NP[rad]; rad=NP[rad]);
	for(; i!=NP[i]; ){
		z=NP[i];
		NP[i]=rad;
		i=z;
	}
	return rad;
}

void uneste(int x, int y){
	NP[x]=y;
}

void citeste(){
	a=fscanf(fpi, "%d %d", &n, &m);
	for(i=0; i<m; i++){
		a=fscanf(fpi, "%d %d %d", &E1[i], &E2[i], &EC[i]);
		Ei[i]=i;
	}
}

void kruskal(){
	for(i=1; i<=n; i++)
		NP[i]=i;
	sort(Ei, Ei+m, compara);
	for(i=0; msel<n-1; i++){
		a=gaseste(E1[Ei[i]]);
		b=gaseste(E2[Ei[i]]);
		if(a != b){
			ES[msel++]=Ei[i];
			sum+=EC[Ei[i]];
			uneste(a, b);
		}
	}
}

void afiseaza(){
	fpo<<sum<<endl<<msel<<endl;
	for(i=0; i<msel; i++)
		fpo<<E1[ES[i]]<<" "<<E2[ES[i]]<<endl;
}

int main(){
	citeste();
	kruskal();
	afiseaza();
	return 0;
}