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

using namespace std;

int root(int v, vector<int> &parent, int &size)
{
	size = 1;
	while (v != parent[v]) {
		v = parent[v];
		size++;
	}
	return v;
}

void bind(int u, int v, vector<int> &parent)
{
	while (true) {
		int p = parent[u];
		parent[u] = v;
		v = u;
		u = p;
		if (parent[u] == u) {
			parent[u] = v;
			break;
		}
	}
}

int build_tree(int n, vector<tuple<int, int, int>> &edges,
				vector<tuple<int, int>> &tree)
{
	vector<int> parent(n);
	for_each(parent.begin(), parent.end(), [i = 0] (auto &p) mutable {
		p = i++;
	});

	sort(edges.begin(), edges.end(), [](auto &e1, auto &e2) {
		return get<2>(e1) < get<2>(e2);
	});

	int min_cost = 0;

	for (const auto &e : edges) {
		int u = get<0>(e);
		int v = get<1>(e);
		int size1, size2;
		int root1 = root(u, parent, size1);
		int root2 = root(v, parent, size2);
		if (root1 != root2) {
			if (size1 <= size2)
				bind(u, v, parent);
			else
				bind(v, u, parent);

			tree.push_back({u, v});
			min_cost += get<2>(e);
		}
	}

	return min_cost;
}

int main()
{
	ifstream in("apm.in");
	ofstream out("apm.out");

	int n, m;
	in >> n >> m;

	int v1, v2, c;
	vector<tuple<int, int, int>> edges(m);
	for (int i = 0; i < m; i++) {
		in >> v1 >> v2 >> c;
		edges[i] = {v1 - 1, v2 - 1, c};
	}

	vector<tuple<int, int>> tree;
	int min_cost = build_tree(n, edges, tree);
	out << min_cost << '\n';
	out << tree.size() << '\n';
	for (const auto &e : tree)
		out << get<0>(e) + 1 << ' ' << get<1>(e) + 1 << '\n';

	in.close();
	out.close();
	return 0;
}