#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
 
int n, m;
std::vector<int> parent;
std::vector<int> height;

int parent_tree(int node, std::vector<int>& parent) {
	while (node != parent[node])
		node = parent[node];
	return node;
}

void union_trees(int parent_1, int parent_2, std::vector<int>& parent, std::vector<int>& height) {
	if (height[parent_1] < height[parent_2]) {
		parent[parent_1] = parent_2;
	} else if (height[parent_1] > height[parent_2]) {
		parent[parent_2] = parent_1;
	} else {
		parent[parent_2] = parent_1;
		height[parent_2]++;
	}
}

void Kruskal(std::vector< std::pair< int, std::pair<int,int> > >& edges) {
	std::ofstream fout("apm.out", std::ofstream::out);

	int total_cost = 0;
	parent = std::vector<int>(n + 1);
	height = std::vector<int>(n + 1, 0);
	std::vector<std::pair<int, int> > result;

	for (int i = 1; i <= n; i++)
		parent[i] = i;

	std::sort(edges.begin(), edges.end());

	for (int i = 0; i < m; i++) {
		int parent_1 = parent_tree(edges[i].second.first, parent);
		int parent_2 = parent_tree(edges[i].second.second, parent);

		if (parent_1 != parent_2) {
			union_trees(parent_1, parent_2, parent, height);
			total_cost += edges[i].first;
			result.push_back(edges[i].second);
		}
	}
	
	fout << total_cost << '\n' << result.size() << '\n';
	for (auto edge: result)
		fout << edge.first << ' ' << edge.second << '\n';
}

int main() {
	
	std::ifstream fin("apm.in", std::ifstream::in);
	

	std::vector< std::pair< int, std::pair<int,int> > > edges;
	
	fin >> n >> m;
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < m; i++) {
		fin >> tmp1 >> tmp2 >> tmp3;

		edges.push_back(std::make_pair(tmp3, std::make_pair(tmp2, tmp1)));
	}

	Kruskal(edges);
	
}