#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

class disjointSet {
	int num_elem;
	int* tree_father;
	int* tree_depth;
public:
	disjointSet(int num_elem) {
		this->num_elem = num_elem;
		tree_father = new int[num_elem];
		tree_depth = new int[num_elem];
		for (int i = 0; i < num_elem; i++) {
			tree_father[i] = i;	
			tree_depth[i] = 0;
		}
	}
	~disjointSet() {
		delete tree_father;
		delete tree_depth;
	}

	int find_root (int elem) {
		int root = elem;
		while (tree_father[root] != root)
			 root = tree_father[root];
		return tree_father[elem] = root;		
	}

	bool join (int elem1, int elem2) {
		int root1 = find_root(elem1);
		int root2 = find_root(elem2);
		
		/* check if they are in the same set */
		if (root1 == root2)
			return false;

		if (tree_depth[root1] < tree_depth[root2])
			tree_father[root1] = root2;
		else if (tree_depth[root1] > tree_depth[root2])
				tree_father[root2] = root1;
		     else
				tree_father[root2] = root1, tree_depth[root1]++;
		return true;
	}
};

class graph {
	struct edge {
		int node_1, node_2;
		int cost;
		edge (int node_1, int node_2, int cost) {
			this->node_1 = node_1;	
			this->node_2 = node_2;	
			this->cost = cost;	
		}

		bool operator <(const edge& X) {
			return this->cost < X.cost;
		}
	};
	int num_nodes;
	vector<edge> Edges;

 public:
	graph (int num_nodes) {
		this->num_nodes = num_nodes;
	}
	
	void add_edge (int node_1, int node_2, int cost) {
		Edges.push_back(edge(node_1, node_2, cost));
	}
	
	void print_apm() {
		/* sort the edges */
		sort(Edges.begin(), Edges.end());
		
		/* create disJoint Set */
		disjointSet S(num_nodes);

		/* APM */
		vector<edge> APM;
		int apm_cost = 0;
		
		for (vector<edge>::iterator it = Edges.begin(); it != Edges.end(); it++) {
			if (S.join(it->node_1, it->node_2)) {
				apm_cost += it->cost;
				APM.push_back(*it);
				if (APM.size() == num_nodes - 1)
					break;
			}
		}

		printf("%d\n", apm_cost);
		printf("%d\n", num_nodes - 1);
		for (vector<edge>::iterator it = APM.begin(); it != APM.end(); it++)
			printf("%d %d\n", it->node_1, it->node_2);		
	}
};

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	
	int num_nodes, num_edges;

	scanf("%d %d", &num_nodes, &num_edges);

	graph G(num_nodes);

	for (int i = 0; i < num_edges; i++) {
		int node_1, node_2, cost;
		scanf("%d %d %d", &node_1, &node_2, &cost);
		G.add_edge(node_1, node_2, cost);
	}

	G.print_apm();

	return 0;
}