#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>

const int dim = 200001;
int t[dim];
class Muchie;
std::vector<Muchie>v;
std::vector<Muchie>sol;
int noduri, muchii;

void init() {
	for (int i = 1; i <= noduri; i++) {
		t[i] = i;
	}
}

void unit(int i, int j) {
	t[j] = i;
}

int root(int nod) {

	int R = nod, next;
	while (R != t[R]) {
		R = t[R];
	}
	//in R am radacina
	while (nod != t[nod]) {
		next = t[nod];
		t[nod] = R;
		nod = next;
	}

	return R;
}

class Muchie {
public:
	int i;
	int j;
	int cost;
	Muchie(int i, int j, int cost) : i{ i }, j{ j }, cost{ cost } {

	}
};

struct cmp {
	bool operator()(Muchie i, Muchie j) {
		return i.cost < j.cost;
	}
}cmpf;

void input() {
	std::ifstream in("apm.in");
	in >> noduri >> muchii;
	for (int ii = 0; ii < muchii; ii++) {
		int i, j, cost;
		in >> i >> j >> cost;
		Muchie m{ i, j, cost };
		v.push_back(m);
	}
}

int main() {
	int cost = 0;
	input();
	init();
	std::sort(v.begin(), v.end(), cmpf);
	
	/*
	for (auto& el : v) {
		std::cout << el.i << " " << el.j << " " << el.cost << "\n";
	}
	*/
	
	
	for (auto& el : v) {
		if (root(el.i) != root(el.j)) {
			unit(root(el.i), root(el.j));
			sol.push_back(el);
			cost += el.cost;
		}
	}
	
	std::ofstream out("apm.out");
	out << cost << "\n";
	out << sol.size() << "\n";

	for (auto& el : sol) {
		out << el.i << " " << el.j <<"\n";
	}

	return 0;
}