#include <algorithm>
#include <cassert>
#include <cstdio>
#include <map>
#include <vector>

#define MAXN 200000

struct ele {
	int i;
	int j;
	ele() = default;
	ele(int a, int b):i(a),j(b) {}
};

std::map<int, std::vector<ele>> muchii;

int n, m;

int comp[MAXN];
int ret_sum[MAXN];
ele ret_muchii[MAXN];
int ret_length;

void join (int a, int b, int pret) {
	int i;
	int to = std::min(comp[a], comp[b]);
	int from = std::max(comp[a], comp[b]);

	for (i = 0; i != n; ++ i)
		if (comp[i] == from)
			comp[i] = to;

	/*
	{
		int x;
		x = ret_sum[comp[from]] + ret_sum[comp[to]] + pret;
		fprintf(stderr, "Joining %d and %d", to, from);
		fprintf(stderr, "  - making the new cost %d, from %d + %d + %d\n",
			x, ret_sum[comp[from]], ret_sum[comp[to]], pret);
	}
	*/
	ret_sum[to] = ret_sum[from] + ret_sum[to] + pret;
	ret_muchii[ret_length ++] = {a + 1, b + 1};
}


int main () {
	int i;

	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d%d", &n, &m);

	for (i = 0; i != m; ++ i) {
		int de, la, pret;
		scanf("%d%d", &de, &la);
		-- de, -- la;
		scanf("%d", &pret);

		muchii[pret].emplace_back(de, la);
	}

	for (i = 0; i != n; ++ i)
		comp[i] = i;

	for (const auto &p: muchii) {
		for (auto [de, la]: p.second) {
			if (comp[de] == comp[la])
				continue;
			join(de, la, p.first);
		}
	}

	/*
	for (i = 0; i != n; ++ i) {
		fprintf(stderr, "%d ", comp[i]);
	}
	putchar('\n');

	for (i = 0; i != n; ++ i)
		assert(comp[i] == 0);

	assert(ret_length == n - 1);
	*/

	printf("%d\n", ret_sum[0]);

	printf("%d\n", ret_length);

	for (i = 0; i != ret_length; ++ i)
		printf("%d %d\n", ret_muchii[i].i, ret_muchii[i].j);
}