#include <iostream>
#include <fstream>
#include <stdint.h>
#include <algorithm>

const int32_t MAX_N = 200000;
const int32_t MAX_M = 400000;

struct Edge {
	int32_t node1;
	int32_t node2;
	int32_t cost;

	bool operator<(const Edge& other) const {
		if(cost != other.cost)
			return cost < other.cost;
		if(node1 != other.node1)
			return node1 < other.node1;
		return node2 < other.node2;
	}
};
struct ResEdge {
	int32_t node1, node2;
};

struct DisjointSetForest {
	int32_t n;
	int32_t parents[MAX_N], depths[MAX_N];

	void Init(int32_t n) {
		this->n = n;
		for(int32_t i = 0; i != n; ++i)
			parents[i] = -1;
		for(int32_t i = 0; i != n; ++i)
			depths[i] = 1;
	}
	int32_t GetRoot(int32_t node) {
		if(parents[node] == -1)
			return node;
		parents[node] = GetRoot(parents[node]);
		return parents[node];
	}
	void Merge(int32_t root1, int32_t root2) {
		if(depths[root1] > depths[root2]) {
			parents[root2] = root1;
		} else if(depths[root2] > depths[root1]) {
			parents[root1] = root2;
		} else {
			parents[root2] = root1;
			++depths[root1];
		}
	}
};

int32_t n, m;
Edge edges[MAX_M];
DisjointSetForest dsf;
ResEdge mst[MAX_N - 1]; int32_t top = 0, totalCost = 0;

void ReadTree(std::istream& fin) {
	fin >> n >> m;
	for(int32_t i = 0; i != m; ++i) {
		fin >> edges[i].node1 >> edges[i].node2 >> edges[i].cost;
		--edges[i].node1; --edges[i].node2;
	}
}
void BuildMST() {
	std::sort(edges, edges + m);
	dsf.Init(n);

	for(int32_t i = 0; i != m && top != n - 1; ++i) {
		Edge edge = edges[i];

		int32_t root1 = dsf.GetRoot(edge.node1);
		int32_t root2 = dsf.GetRoot(edge.node2);

		if(root1 != root2) {
			dsf.Merge(root1, root2);
			
			mst[top++] = { edge.node1, edge.node2 };
			totalCost += edge.cost;
		}
	}
}
void OutputRes(std::ostream& fout) {
	fout << totalCost << '\n' << top << '\n';
	for(int32_t i = 0; i != top; ++i)
		fout << (mst[i].node1 + 1) << ' ' << (mst[i].node2 + 1) << '\n';
}

int main() {
	std::ifstream fin("apm.in");
	std::ofstream fout("apm.out");

	ReadTree(fin);
	BuildMST();
	OutputRes(fout);

	fin.close();
	fout.close();

	return 0;
}