#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 x, y, c;
};

Edge edges[MAX_M];
bool edgeUsed[MAX_M];
int32_t parents[MAX_N], sizes[MAX_N];

bool CompEdges(const Edge& edge1, const Edge& edge2) {
	return edge1.c < edge2.c;
}
int32_t GetRoot(int32_t node) {
	while(parents[node] != -1)
		node = parents[node];
	return node;
}
void Merge(int32_t root1, int32_t root2) {
	if(sizes[root1] > sizes[root2]) {
		parents[root2] = root1;
	} else if(sizes[root2] > sizes[root1]) {
		parents[root1] = root2;
	} else {
		parents[root2] = root1;
		++sizes[root1];
	}
}

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

	int32_t n, m;
	fin >> n >> m;

	for(int32_t i = 0; i != m; ++i) {
		fin >> edges[i].x >> edges[i].y >> edges[i].c;
		--edges[i].x;
		--edges[i].y;
	}

	for(int32_t i = 0; i != n; ++i)
		parents[i] = -1;
	std::sort(edges, edges + m, CompEdges);

	int32_t totalCost = 0;
	for(int32_t i = 0; i != m; ++i) {
		int32_t root1 = GetRoot(edges[i].x), root2 = GetRoot(edges[i].y);
		if(root1 == root2)
			continue;
		
		totalCost += edges[i].c;
		edgeUsed[i] = true;
		Merge(root1, root2);
	}

	fout << totalCost << '\n' << (n - 1) << '\n';
	for(int32_t i = 0; i != m; ++i) {
		if(edgeUsed[i])
			fout << (edges[i].x + 1) << ' ' << (edges[i].y + 1) << '\n';
	}

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

	return 0;
}