#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int maxn=400100;
vector<vector<int>>ls,apm;
int tata[maxn];
int h[maxn];

int radacina(int nod) {
	if (tata[nod] == 0)
		return nod;
	tata[nod] = radacina(tata[nod]);
	return tata[nod];
}

void reuniune(int nod1, int nod2) {
	nod1 = radacina(nod1);
	nod2 = radacina(nod2);
	if (h[nod1] > h[nod2]) {
		tata[nod2] = nod1;
	}
	else {
		tata[nod1] = nod2;
		if (h[nod1] == h[nod2])
			h[nod2]++;
	}
}

int main() {

	int n, m,k=0,total=0;
	in >> n >> m;
	while (m--) {
		int v1, v2, c;
		in >> v1 >> v2 >> c;
		ls.push_back({ c,v1,v2 });
		k++;
	}

	sort(ls.begin(), ls.end());

	for (auto muchie :ls)
	{
		int nod1 = muchie[1];
		int nod2 = muchie[2];
		int cost = muchie[0];
		if (radacina(nod1) != radacina(nod2)) {
			total += cost;
			reuniune(nod1, nod2);
			apm.push_back({ nod1,nod2 });
		}
	}
	out << total << "\n" << n - 1 << "\n";
	for (auto x : apm) {
		out << x[0] << " " << x[1] << "\n";
	}

	return 0;
}