#include <fstream>
#include <algorithm>
#define NMAX 400100

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int N,M,X[NMAX],Y[NMAX],GR[NMAX],C[NMAX],IND[NMAX],rs,k,RS[NMAX];

int find(int x){
	if(GR[x] == x) return x;
	GR[x] = find(GR[x]);
	return GR[x];
}

void unit(int x, int y){GR[find(x)] = find(y);}
bool comp(int a, int b){return C[a] < C[b];}

int main(){
	fin >> N >> M;
	for(int i = 1;i<=M;i++){
		fin >> X[i] >> Y[i] >> C[i];
		IND[i] = i;
	}
	for(int i = 1;i<=N;i++) GR[i] = i;
	sort(IND+1,IND+M+1,comp);
	for(int i = 1;i<=M;i++){
		if(find(X[IND[i]]) != find(Y[IND[i]])){
			rs+=C[IND[i]];
			RS[k++]  = IND[i];
			unit(X[IND[i]],Y[IND[i]]);			
		}
	}
	fout << rs << '\n' << k << '\n';
	for(int i = 0;i<k;i++) fout << X[RS[i]] << ' ' << Y[RS[i]] << '\n';
	return 0;
}