#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
#define MAX_SIZE 200001
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_queue;
vector<int> minimum_spanning_tree[MAX_SIZE];
queue<pair<int, int>> edges_list;
bool is_path;

void check_path(int current_node, int goal_node, bool is_visited[]) {
	is_visited[current_node] = true;
	int length = minimum_spanning_tree[current_node].size();
	for (int i = 0; i < length; ++i) {
		if (!is_visited[minimum_spanning_tree[current_node][i]]) {
			if (minimum_spanning_tree[current_node][i] == goal_node) {
				is_path = true;
				return;
			}
			check_path(minimum_spanning_tree[current_node][i], goal_node, is_visited);
		}
	}
}

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;
		ordered_queue.push({edge_cost, node_1, node_2});
	}
	int spanning_tree_cost = 0;
	while (ordered_queue.size() && edges_list.size() != nr_nodes) {
		node_1 = get<1>(ordered_queue.top());
		node_2 = get<2>(ordered_queue.top());
		edge_cost = get<0>(ordered_queue.top());
		bool is_visited[MAX_SIZE] = { false };
		is_path = false;
		check_path(node_1, node_2, is_visited);
		if (!is_path) {
			spanning_tree_cost += edge_cost;
			minimum_spanning_tree[node_1].push_back(node_2);
			minimum_spanning_tree[node_2].push_back(node_1);
			edges_list.push({node_2, node_1});
		}
		ordered_queue.pop();
	}
	fout << spanning_tree_cost << '\n' << edges_list.size() << '\n';
	while (!edges_list.empty()) {
		fout << edges_list.front().first << ' ' << edges_list.front().second << '\n';
		edges_list.pop();
	}
	return 0;
}