/*
	Motivul pentru care e nevoie sa retin nodul principal(tata) a nodului din muchia curenta care face parte din componenta conexa cu mai putine noduri, sau egale cu cu numarul de noduri din cealalta componenta conexa este urmatorul:
	In interiorul for - ului eu verificam vecinii nodului cu valoare egala cu labelul nodului curent.
	Avand in vedere ca in interiorul forului se face procesul de unire a 2 componente conexe, fiecare vecin din componenta conexa mai mica 
	va primi labelul nodului tata din componenta mai mare. 
	Astfel, daca instructiunea for se executa inca o data, eu in loc sa parcurg vecinii nodului cu valoare egala cu labelul nodului curent, as verifica 
	vecinii nodului tata din componenta conexa mai mare, si i-as adauga din nou in componenta conexa mai mare, iar nodurile din componenta conexa mai mica ar ramane neadaugate, exceptand primul nod din componenta conexa.

	Asa retin nodul tata din componenta conexa mai mica:
	int node = node_1;
	if (node_labels[node_1] != node_1) {
		node = node_labels[node_1];
	}
*/
#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();
				int father_node = node_labels[node_2];
				for (int i = 0; i < length; ++i) {
					int neighbour = connected_components[father_node][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();
				int father_node = node_labels[node_1];
				for (int i = 0; i < length; ++i) {
					int neighbour = connected_components[father_node][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_1, node_2 });
		}
		ordered_edges_queue.pop();
	}
	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();
	}
	return 0;
}