#include<iostream>
#include<vector>
#include<fstream>
#include<tuple>
#include<algorithm>
std::ifstream in("apm.in");
std::ofstream out("apm.out");
using namespace std;
int n, m, suma;
vector<tuple<int, int, int>>g;
vector<int> dim, t;
vector<pair<int, int>>ans;
bool cmp(tuple<int, int, int>a, tuple<int, int, int>b) {
	int x, y, cost;
	tie(x, y, cost) = a;
	int x1, y1, cost1;
	tie(x1, y1, cost1) = b;
	return cost < cost1;
}
int root(int x) {
	if (x == t[x]) return x;
	else return t[x] = root(t[x]);
}
void union_set(int a, int b) {
	a = root(a), b = root(b);
	if (dim[a] < dim[b]) t[a] = b, dim[b]++;
	else t[b] = a, dim[a]++;
}
int main() {
	in >> n >> m;
	dim = t = vector<int>(n + 1);
	for (int i = 1; i <= n; i++) dim[i] = 1, t[i] = i;
	while (m--) {
		int u, v, cost;
		in >> u >> v >> cost;
		g.push_back({ u, v, cost });
	}
	sort(g.begin(), g.end(), cmp);
	for (auto i : g) {
		int x, y, cost;
		tie(x, y, cost) = i;
		if (root(x) != root(y)) suma += cost, union_set(x, y), ans.push_back({ x,y });
	}
	out << suma << '\n';
	out << ans.size() << '\n';
	for (auto i : ans) out << i.second << " " << i.first << '\n';
	return 0;
}