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

struct Edge {
	int x, y, cost;

	bool operator<(const Edge& edge) const {
		return cost < edge.cost;
	}
};

std::vector<Edge> Edges;
std::vector<std::pair<int, int>> APM;

int t[200001];
int rang[200001];
int Cost = 0;

int GetRoot(int k) {
	if (t[k] == k)
		return k;

	int root = GetRoot(t[k]);
	t[k] = root;
	return root;
}

bool SameRoot(int x, int y) {
	return GetRoot(x) == GetRoot(y);
}

void Unite(int x, int y) {
	int rx = GetRoot(x);
	int ry = GetRoot(y);

	if (rx == ry)
		return;

	if (rang[rx] > rang[ry])
		t[ry] = rx;
	else {
		t[rx] = ry;

		if (rang[rx] == rang[ry])
			++rang[ry];
	}
}

void kruskal() {
	int x, y, cost;

	for (auto& edge : Edges) {
		x = edge.x;
		y = edge.y;
		cost = edge.cost;

		if (SameRoot(x, y))
			continue;

		Unite(x, y);

		Cost += cost;
		APM.push_back({ x, y });
	}
}

int main() {
	std::ifstream fin("apm.in");
	std::ofstream fout("apm.out");

	int N, M;
	fin >> N >> M;

	int X, Y, C;

	for (int i = 1; i <= M; ++i) {
		fin >> X >> Y >> C;

		Edges.push_back({ X, Y, C });
	}

	fin.close();

	std::sort(Edges.begin(), Edges.end());

	for (int i = 1; i <= N; ++i)
		t[i] = i;

	kruskal();

	fout << Cost << '\n';
	fout << APM.size() << '\n';

	for (auto& edge : APM)
		fout << edge.first << ' ' << edge.second << '\n';

	fout.close();

	return 0;
}