#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define pi std::pair<int,int>
#define ppi std::pair<int, pi>
#define x first
#define y second

const int nmax = 2e5 + 5;

int tata[nmax], sz[nmax];
std::vector<pi>ans_pairs;

int extreme(int node) {
	int t = node;
	while (tata[t] != t) t = tata[t];
	tata[node] = t;
	while (tata[node] != node) node = tata[node], tata[node] = t;
	return t;
}

void connect(int u, int v) {
	int su = extreme(u), sv = extreme(v);
	if (sz[su] < sz[sv]) std::swap(su, sv);
	tata[sv] = su, sz[su] += sz[sv];
}

bool is_connected(int u, int v) {
	return extreme(u) == extreme(v);
}

int main() {
	std::ifstream fin("apm.in");
	std::ofstream fout("apm.out");
	int n, m, ans = 0;
	fin >> n >> m;
	std::vector<ppi>l(m);
	for (int i = 0; i < m; i++) fin >> l[i].y.x >> l[i].y.y >> l[i].x;
	for (int i = 1; i <= n; i++) sz[i] = 1, tata[i] = i;
	std::sort(l.begin(), l.end());
	for(auto a:l)
		if (!is_connected(a.y.x, a.y.y)) {
			ans += a.x;
			connect(a.y.x, a.y.y);
			ans_pairs.push_back(a.y);
		}
	fout << ans << "\n";
	fout << ans_pairs.size() << "\n";
	for (auto a : ans_pairs) fout << a.x << " " << a.y << "\n";
}