#define _CRT_SECURE_NO_WARNINGS

#include <cmath>
#include <cstdio>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstdio>
using namespace std;

int uf_find(std::vector<int> &head, int u) {
	while (head[u] != -1)
		u = head[u];
	return u;
}

void uf_union(std::vector<int> &head, int u, int v) {
	head[u] = v;
}

int main() {
	/* Enter your code here. Read input from STDIN. Print output to STDOUT */

	int n, m;

	FILE *in = fopen("apm.in", "r");
	fscanf(in, "%d %d", &n, &m);

	std::vector<std::pair<std::pair<int, bool>, std::pair<int, int>>> edges;

	for (int i = 0; i < m; i++) {
		int u, v, c;
		fscanf(in, "%d %d %d", &u, &v, &c);
		u = u - 1;
		v = v - 1;
		edges.push_back({ {c, false} ,{ u, v} });
	}
	fclose(in);
	std::sort(edges.begin(), edges.end());

	std::vector<int> head(n, -1);
	int cost = 0;

	for (auto &edge : edges) {
		int u = uf_find(head, edge.second.first);
		int v = uf_find(head, edge.second.second);
		if (u != v) {
			uf_union(head, u, v);
			cost += edge.first.first;
			edge.first.second = true;;
		}
	}

	FILE *out = fopen("apm.in", "w");
	fprintf(out, "%d\n", cost);
	fprintf(out, "%d\n", n - 1);
	for (auto const &edge : edges) {
		if (edge.first.second) {
			fprintf(out, "%d %d\n", edge.second.first + 1, edge.second.second + 1);
		}
	}
	fclose(out);

	return 0;
}