#include <vector>
#include <fstream>
#include <iostream>
#define MAXN 200010
using namespace std;

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

int L[MAXN];
struct Edge {
	int x,y,cost;
};
vector<Edge> E;
vector<Edge> APM;
int N,M;
int nr,cost;

bool compare(Edge a,Edge b) {
	return (a.cost < b.cost);
}

int read() {
	int i;
	fin >> N >> M;
	E.resize(M);
	for (i=0;i<M;++i) {
		fin >> E[i].x >> E[i].y >> E[i].cost;
	}
	sort(E.begin(),E.end(),compare);
	for (i=0;i<N;++i) {
		L[i] = i;
	}
}

int calc() {
	int i,j,Lx,Ly;
	for (i=0;i<M;++i) {
		if (L[E[i].x] != L[E[i].y]) {
			APM.push_back(E[i]);
			cost += E[i].cost;
			Lx = min(L[E[i].x],L[E[i].y]);
			Ly = max(L[E[i].x],L[E[i].y]);
			for (j=0;j<N;++j)
				if (L[j] == Ly) L[j] = Lx;
		}
	}
}

int write() {
	int i;
	fout << cost << "\n";
	fout << APM.size() << "\n";
	for (i=0;i<APM.size();++i) {
		fout << APM[i].x << " " << APM[i].y << "\n";
	}
}

int main() {
	
	read();
	calc();
	write();
	
	fin.close();
	fout.close();
	return 0;
}