#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

struct Muchie {
	int x, y, c;
};
 
std::vector<Muchie>muchii;  
int N, M;

void citire() {
	std::ifstream f("apm.in");
	f >> N >> M;
	muchii.reserve(M);

	for (int i = 0; i < M; ++i) {
		int x, y, c;
		f >> x >> y >> c;
		
		muchii.push_back({ x,y,c });
	}
}

int t[100000], h[100000];

int Find(int x) {
	int r = x;
	while (t[r] != r)r = t[r];

	while (x != r) {
		int temp = t[x];
		t[x] = r;
		x = temp;
	}
	return x;
}

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	if (h[x] < h[y]) {
		t[x] = y;
	}
	else {
		t[y] = x;
		if (h[x] == h[y])h[x]++;
	}
}

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

	std::sort(muchii.begin(), muchii.end(), [](const Muchie& a, const Muchie& b) { return a.c < b.c; });

	std::vector<std::pair<int,int> > res;
	res.reserve(N-1);

	int selectedEdges = 0, cmin = 0;

	for (const Muchie& m : muchii) {
		if (selectedEdges == N - 1)break;
		if (Find(m.x) == Find(m.y))continue;

		selectedEdges++;
		cmin += m.c;
		Union(m.x, m.y);
		res.push_back({ m.x,m.y });
	}

	std::ofstream g("apm.out");
	g << cmin << '\n' << res.size() << '\n';
	for (auto m : res) {
		g << m.first << ' ' << m.second << '\n';
	}
}

int main()
{

	citire();

	sol();

}