#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
#define MAX_NR_NODES 200000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> ordered_edges_queue;
queue<pair<int, int>> minimum_spanning_tree_edges;
vector<int> connected_components[MAX_NR_NODES + 1];
int node_labels[MAX_NR_NODES + 1];

int main() {
	int nr_nodes, nr_edges;
	fin >> nr_nodes >> nr_edges;
	int node_1, node_2, edge_cost;
	for (int edge = 0; edge < nr_edges; ++edge) {
		fin >> node_1 >> node_2 >> edge_cost;

		if (!node_labels[node_1]) {
			node_labels[node_1] = node_1;
			connected_components[node_1].push_back(node_1);
		}
		if (!node_labels[node_2]) {
			node_labels[node_2] = node_2;
			connected_components[node_2].push_back(node_2);
		}

		ordered_edges_queue.push({edge_cost, node_1, node_2});
	}
	int spanning_tree_cost = 0;
	while (ordered_edges_queue.size() && minimum_spanning_tree_edges.size() != nr_nodes - 1) {
		node_1 = get<1>(ordered_edges_queue.top());
		node_2 = get<2>(ordered_edges_queue.top());
		edge_cost = get<0>(ordered_edges_queue.top());
		if (node_labels[node_1] != node_labels[node_2]) {
			if (connected_components[node_labels[node_1]].size() >= connected_components[node_labels[node_2]].size()) {
				int length = connected_components[node_labels[node_2]].size();
				for (int i = 0; i < length; ++i) {
					int neighbour = connected_components[node_labels[node_2]][i];
					connected_components[node_labels[node_1]].push_back(neighbour);
					node_labels[neighbour] = node_labels[node_1];
				}
			} else {
				int length = connected_components[node_labels[node_1]].size();
				for (int i = 0; i < length; ++i) {
					int neighbour = connected_components[node_labels[node_1]][i];
					connected_components[node_labels[node_2]].push_back(neighbour);
					node_labels[neighbour] = node_labels[node_2];
				}
			}
			spanning_tree_cost += edge_cost;
			minimum_spanning_tree_edges.push({ node_2, node_1 });
		}
		ordered_edges_queue.pop();
	}
	fout << spanning_tree_cost << '\n' << minimum_spanning_tree_edges.size() << '\n';
	while (!minimum_spanning_tree_edges.empty()) {
		fout << minimum_spanning_tree_edges.front().first << ' ' << minimum_spanning_tree_edges.front().second << '\n';
		minimum_spanning_tree_edges.pop();
	}
	return 0;
}