#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

struct muchie {

	int x, y, cost;
};


int cmp(muchie a, muchie b) {
	if (a.cost < b.cost) return 1;
	return 0;
}

int main() {

	int n, m;
	f >> n >> m;
	muchie altceva;
	vector <muchie> muie;
	vector <muchie> sol;
	vector <int> comp(n + 1);
	vector <vector <int>> lista(n + 1);

	for (int i = 1; i <= n; i++) {
		comp[i] = i;
		lista[i].push_back(i);
	}

	for (int i = 0; i < m; i++) {
		f >> altceva.x >> altceva.y >> altceva.cost;
		muie.push_back(altceva);
	}

	sort(muie.begin(), muie.end(), cmp);

	int cost = 0;
	for (auto m : muie) {
		int compx = comp[m.x];
		int compy = comp[m.y];

		if (compx != compy) {
			cost += m.cost;
			sol.push_back(m);

			for (auto x : lista[compx]) {
				comp[x] = compy;
				lista[compy].push_back(x);
			}
		}
	}

	g << cost << '\n' << n - 1 << '\n';
	for (auto s : sol) {
		g << s.x << ' ' << s.y << '\n';
	}
	return 0;
}