#include <iostream>
#include <fstream>
#include <vector>
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;
		return true;
	}
};
///Vector for edges
struct edge {
	int x, y;
	int cost;
};
std::vector<edge> v;
///End of vector for edges

///Begin of quickSort
int partition(int left, int right) {
	int i = left;
	int j = right;
	int pivot = v[(left + right) / 2].cost;

	while (i <= j) {
		while (v[i].cost < pivot)
			++i;
		while (v[j].cost > pivot)
			--j;
		if (i <= j) {
			std::swap(v[i], v[j]);
			++i;
			--j;
		}
	}

	return i;
}
void quickSort(int left, int right) {
	int index = partition(left, right);
	if (left < index - 1)
		quickSort(left, index - 1);
	if (index < right)
		quickSort(index, right);
}
///End of quickSort

///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);
	}

	quickSort(1, m);

	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;
}