#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) {
	int h = u;
	while (head[h] != -1)
		h = head[h];

	while (head[u] != -1) {
		int t = head[u];
		head[u] = h;
		u = t;
	}
	return u;
}


void uf_union(std::vector<int> &head, std::vector<int> &rank, int u, int v) {
	u = uf_find(head, u);
	v = uf_find(head, v);

	if (u == v)
		return;

	if (rank[u] > rank[v])
		head[u] = v;
	else if (rank[u] < rank[v])
		head[v] = u;
	else {
		head[u] = v;
		rank[u]++;
	}
}

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);
	std::vector<int> rank(n, 0);
	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,rank, u, v);
			cost += edge.first.first;
			edge.first.second = true;;
		}
	}

	FILE *out = fopen("apm.out", "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;
}