#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
#define MAX_N 200000
#define MAX_M 400000
struct muchie{
	long x, y, cost;
};

long n, m, padure[MAX_N];
muchie vec[MAX_M];
vector<long> final;

//-----===========QUICK SORT =========--------//
int position(int li, int ls){
	short int mod =1;
	while(li < ls){
		if(vec[li].cost > vec[ls].cost){
			swap(vec[li], vec[ls]);
			mod *=(-1);
		}
		
		if(mod == 1) li++;
		else ls--;
	}
	
	return li;
}


void quick(int li, int ls){
	if(li< ls){
		int lm  = position(li,ls);
		quick(li, lm-1);
		quick(lm+1, ls);
	}
}
//-------QUICK_SORT------------////


int main(){

	ifstream fin("apm.in");
	ofstream fout("apm.out");
	fin >> n >> m;
	
	for(long i=0; i<m; i++){
		long a, b, c; 
		fin >> a >> b >> c;
		vec[i].x = a, vec[i].y = b, vec[i].cost = c;
	}
	
	quick(0,m-1); // sortez vectorul vec dupa costul muchiei
	
	
	/// formez padure
	for(long i=1; i<=n; i++){
		padure[i] = i;
	}

	long cost_final = 0;
	bool continua = false;
	long index = -1;
	while(!continua && index !=m-1){
		index ++;
		if(padure[vec[index].x]!= padure[vec[index].y]){
			long radacina =  padure[vec[index].y];
			continua = true;
			for(long i=1; i<=n; i++){
				if(padure[i] == radacina)
					padure[i] = padure[vec[index].x];
				else if(padure[i]!=radacina && padure[i]!=padure[vec[index].x])
					continua = false;
			}
			cost_final += vec[index].cost;
			final.push_back(vec[index].x), final.push_back(vec[index].y);
		}
		
	}
	
	fout << cost_final << '\n';
	fout << final.size()/2 << '\n';
	
	for(size_t i=0; i<final.size(); i+=2){
		fout << final[i] << " "<<final[i+1]<<'\n';
	}
	
return 0;
}