#define IA_PROB "apm"

#include <cassert>
#include <cstdio>

#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>

#include <algorithm>


using namespace std;

class Tree {
public:
	struct Edge {
		int x, y, c;
		Edge() { x = y = c = 0; }
		Edge(int x, int y, int c): x(x), y(y), c(c) { }
	};
	struct EdgeCmp {
		bool operator()(const Edge &lhs, const Edge &rhs) const {
			return lhs.c > rhs.c;
		}
	};

private:
	vector<vector<Edge>> edges;
public:
	Tree(int num_nodes) : edges(num_nodes) { }
	int num_nodes() { return edges.size(); }
	void add_edge(int x, int y, int c) {
		edges[x].push_back(Edge(x, y, c));
		edges[y].push_back(Edge(y, x, c));
	}
	vector<Edge> *apm_prim(int &res_cost) {
		res_cost = 0;
		vector<Edge> *res = new vector<Edge>();
		priority_queue<Edge, vector<Edge>, EdgeCmp> edge_heap;
		vector<bool> sel(num_nodes());

		sel[0] = true;
		for (Edge e : edges[0]) {
			edge_heap.push(e);
		}

		for (int i = 0; i < num_nodes() - 1; i++) {
			Edge e;
			do {
				assert(!edge_heap.empty());
				e = edge_heap.top();
				edge_heap.pop();
			} while (sel[e.y]);
			sel[e.y] = true;
			res_cost += e.c;
			res->push_back(e);
			for (Edge e2 : edges[e.y]) {
				if (!sel[e2.y]) {
					edge_heap.push(e2);
				}
			}
		}
		return res;
	}
};


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

	int n, m;
	scanf("%d %d", &n, &m);

	Tree tree(n);
	for (int i = 0; i < m; i++) {
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);
		tree.add_edge(x-1, y-1, c);
	}

	int res_cost;
	vector<Tree::Edge> *res = tree.apm_prim(res_cost);
	printf("%d\n%d\n", res_cost, (int)res->size());
	for (Tree::Edge &e : *res) {
		printf("%d %d\n", e.x+1, e.y+1);
	}

	return 0;
}