#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

const int N=200001;
const int M=400001;

int n,m,comp[N],con[N],cost,rez,nrcomp;
bool sel[N];

struct edge{
	int x,y,cost;
}muchii[M],solutie[M];

void citire(){
	int i;
	in>>n>>m;
	for(i=1;i<=m;++i){
		in>>muchii[i].x>>muchii[i].y>>muchii[i].cost;
	}
}	

inline bool funct(edge a,edge b){
	if(a.cost<b.cost)
		return true;
	return false;
}

void rezolvare(){
	int a,b,c,i;
	sort(&muchii[1],&muchii[m+1],funct);
	for(i=1;i<=m;i++){
		a=muchii[i].x;
		b=muchii[i].y;
		c=muchii[i].cost;
		if(sel[a] && sel[b]){
			if(comp[con[a]]!=comp[con[b]]){
				rez++;
				solutie[rez].x=a;
				solutie[rez].y=b;
				comp[con[b]]=comp[con[a]];
				cost+=c;
				sel[a]=sel[b]=true;
			}
			continue;
		}
		if(sel[a]){
			rez++;
			solutie[rez].x=a;
			solutie[rez].y=b;
			con[b]=con[a];
			cost+=c;
			sel[a]=sel[b]=true;
			continue;
		}
		if(sel[b]){
			rez++;
			solutie[rez].x=a;
			solutie[rez].y=b;
			con[a]=con[b];
			cost+=c;
			sel[a]=sel[b]=true;
			continue;
		}
		rez++;
		solutie[rez].x=a;
		solutie[rez].y=b;
		nrcomp++;
		comp[nrcomp]=nrcomp;
		con[a]=con[b]=nrcomp;
		cost+=c;
		sel[a]=sel[b]=true;
	}
}
	
void afisare(){
	int i;
	out<<cost<<"\n";
	out<<rez<<"\n";
	for(i=1;i<=rez;i++){
		out<<solutie[i].x<<" "<<solutie[i].y<<"\n";
	}
}

int main(){
	citire();
	rezolvare();
	afisare();
	return 0;
}