#include <bits/stdc++.h>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

vector<vector<int>>ls,apm;

int tata[200005], h[200005];

int radacina(int u)
 {
	if (tata[u] == 0)
		return u;
	return tata[u] = radacina(tata[u]);
}

void reuniune(int u, int v) {
	int ru, rv;
	ru = radacina(u);
	rv = radacina(v);
	if (h[ru] < h[rv])
	{
		tata[ru] = rv;
	}
	else {
		tata[rv] = ru;
		if (h[ru] == h[rv])
			h[rv]++;
	}
}

int main() {
	int n, t=0,m;
	in >> n >> m;
	while (m--) {
		int a, b, c;
		in >> a >> b >> c;
		ls.push_back({ c,a,b });

	}
	sort(ls.begin(), ls.end());
	for (auto v : ls) {
		if (radacina(v[1]) != radacina(v[2])) {
			apm.push_back({ v[1],v[2] });
			t += v[0];
			reuniune(v[1], v[2]);
		}
	}

	out << t << "\n" << n - 1 << "\n";
	for (auto v : apm) {
		out << v[0] << " " << v[1] << "\n";
	}
	return 0;
}