#include <fstream>
#include <vector>
#include <algorithm>

std::ifstream f("apm.in");
std::ofstream g("apm.out");

class DisjointForest {
private:
	int *father;
	int *rank;

	int findSet(int node) {
		if (node == father[node])
			return node;
		return father[node] = findSet(father[node]);
	}

public:
	DisjointForest(int numberOfVertices) {
		++numberOfVertices;
		father = new int[numberOfVertices];
		rank = new int[numberOfVertices];
		for (int i = 1; i < numberOfVertices; ++i) {
			father[i] = i;
			rank[i] = 0;
		}
	}

	bool union_(int node1, int node2) {
		if (node1 == node2)
			return false;
		
		node1 = findSet(node1);
		node2 = findSet(node2);

		if (node1 == node2)
			return false;

		if (rank[node1] < rank[node2])
			father[node1] = node2;
		else
			if (rank[node2] < rank[node1])
				father[node2] = node1;
			else {
				father[node1] = node2;
				rank[node2]++;
			}

		return true;
	}
};

struct Edge {
	int x, y;
	int cost;
};
std::vector<Edge> edges;
bool cmp(Edge a, Edge b) {
	return a.cost < b.cost;
}

int main() {
	int n;
	f >> n;

	DisjointForest* forest = new DisjointForest(n);

	int m;
	f >> m;
	Edge k;
	k.x = k.y = k.cost = -1001;
	edges.push_back(k);
	for (int i = 1; i <= m; ++i) {
		f >> k.x >> k.y >> k.cost;
		edges.push_back(k);
	}

	std::sort(edges.begin(), edges.end(), cmp);

	int i = 1;
	int nrMin = n - 1;
	int nr = 0;
	int cost = 0;
	std::vector<Edge> MST;

	while (nr < nrMin) {
		if (forest->union_(edges[i].x, edges[i].y)) {
			MST.push_back(edges[i]);
			cost += edges[i].cost;
			++nr;
		}
		++i;
	}

	g << cost << '\n';
	g << nr << '\n';
	for (int i = 0; i < nr; ++i) {
		g << MST[i].y << " " << MST[i].x << '\n';
	}

	return 0;
}