#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
std::ifstream f("apm.in");
std::ofstream g("apm.out");
class DisjointSet {
private:
	int* father;
	int capacity;

	int findSet(int node) {
		if (node == father[node])
			return node;
		return father[node] = findSet(father[node]);
	}

public:
	DisjointSet(int capacity) {
		this->capacity = capacity;
		father = new int[capacity + 1];
		for (int i = 1; i <= capacity; ++i) {
			father[i] = i;
		}
	}

	bool union1(int node1, int node2) {
		if (node1 == node2)
			return false;

		int set1 = findSet(node1);
		int set2 = findSet(node2);

		if (set1 == set2)
			return false;

		father[set2] = set1;

	}
};
///Vector for edges
struct edge {
	int x, y;
	int cost;
};
std::vector<edge> v;
///End of vector for edges
bool cmp(edge a, edge b) {
	return a.cost < b.cost;
}
///Vector for solution
struct edgeSol {
	int x, y;
};
std::vector<edgeSol> sol;
///End of vector for solution
int main() {
	int n;
	f >> n;

	int m;
	f >> m;

	v.reserve(m + 1);

	edge k;
	k.x = k.y = k.cost = -1001;
	v.push_back(k);

	for (int i = 1; i <= m; ++i) {
		f >> k.x >> k.y >> k.cost;
		v.push_back(k);
	}

	k.x = k.y = k.cost = 1001;
	v.push_back(k);

	std::sort(v.begin(), v.end(), cmp);

	DisjointSet* set = new DisjointSet(n);

	int i = 1;
	int nr = 0;
	int nrMin = n - 1;
	int sum = 0;
	

	while (nr < nrMin) {
		if (set->union1(v[i].x, v[i].y)) {
			sol.push_back({ v[i].x, v[i].y });
			sum += v[i].cost;
			++nr;
		}
		++i;
	}

	g << sum << '\n';

	int sz = sol.size();
	g << sz << '\n';

	for (int i = 0; i < sz; ++i) {
		g << sol[i].x << " " << sol[i].y << '\n';
	}

	return 0;
}