#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];

void sort_graph_edges(int edge_cost, int node_1, int node_2) {
	ordered_edges_queue.push({ edge_cost, node_1, node_2 });
}

void create_initial_components(int node_1, int node_2) {
	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);
	}
}

void scan_input(int nr_edges) {
	int node_1, node_2, edge_cost;
	for (int edge = 0; edge < nr_edges; ++edge) {
		fin >> node_1 >> node_2 >> edge_cost;
		create_initial_components(node_1, node_2);
		sort_graph_edges(edge_cost, node_1, node_2);
	}
}

void add_nodes_to_connected_component_list(int node, int length, int father_node) {
	for (int i = 0; i < length; ++i) {
		int neighbour = connected_components[father_node][i];
		connected_components[node_labels[node]].push_back(neighbour);
		node_labels[neighbour] = node_labels[node];
	}
}

void enlarge_connected_components_list(int node_1, int node_2) {
	int length, father_node, node;
	if (connected_components[node_labels[node_1]].size() > connected_components[node_labels[node_2]].size()) {
		length = connected_components[node_labels[node_2]].size();
		father_node = node_labels[node_2];
		node = node_1;
	} else {
		length = connected_components[node_labels[node_1]].size();
		father_node = node_labels[node_1];
		node = node_2;
	}
	add_nodes_to_connected_component_list(node, length, father_node);
}

void create_minimum_spanning_tree(int* spanning_tree_cost, int nr_nodes) {
	while (!ordered_edges_queue.empty() && minimum_spanning_tree_edges.size() != nr_nodes - 1) {
		int node_1 = get<1>(ordered_edges_queue.top());
		int node_2 = get<2>(ordered_edges_queue.top());
		int edge_cost = get<0>(ordered_edges_queue.top());
		if (node_labels[node_1] != node_labels[node_2]) {
			enlarge_connected_components_list(node_1, node_2);
			spanning_tree_cost += edge_cost;
			minimum_spanning_tree_edges.push({ node_1, node_2 });
		}
		ordered_edges_queue.pop();
	}
}

void print_minimum_spanning_tree_details(int* spanning_tree_cost, int nr_nodes) {
	fout << spanning_tree_cost << '\n' << nr_nodes - 1 << '\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();
	}
}

int main() {
	int nr_nodes, nr_edges;
	fin >> nr_nodes >> nr_edges;
	scan_input(nr_edges);
	int* spanning_tree_cost = 0;
	create_minimum_spanning_tree(spanning_tree_cost, nr_nodes);
	print_minimum_spanning_tree_details(spanning_tree_cost, nr_nodes);
	return 0;
}