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

int uf_find(std::vector<int> &head, int u) {
	while (head[u] != -1)
		u = head[u];
	return u;
}

void uf_union(std::vector<int> &head, int u, int v) {
	head[u] = v;
}

int main() {
	/* Enter your code here. Read input from STDIN. Print output to STDOUT */

	int n, m;

	std::ifstream in("apm.in");
	in >> n >> m;

	std::vector<std::pair<std::pair<int, bool>, std::pair<int, int>>> edges;

	for (int i = 0; i < m; i++) {
		int u, v, c;
		in >> u >> v >> c;
		u = u - 1;
		v = v - 1;
		edges.push_back({ {c, false} ,{ u, v} });
	}
	std::sort(edges.begin(), edges.end());

	std::vector<int> head(n, -1);
	int cost = 0;

	for (auto &edge : edges) {
		int u = uf_find(head, edge.second.first);
		int v = uf_find(head, edge.second.second);
		if (u != v) {
			uf_union(head, u, v);
			cost += edge.first.first;
			edge.first.second = true;;
		}
	}

	std::ofstream out("apm.out");
	out << cost << "\n";
	out << n - 1 << "\n";
	for (auto const &edge : edges) {
		if (edge.first.second) {
			out << edge.second.first + 1 << " " << edge.second.second + 1 << "\n";
		}
	}

	return 0;
}