#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 parinte[MAXN];
int ret_sum[MAXN];
ele ret_muchii[MAXN];
int ret_length;
int ret_rad;

void join (int a, int b, int pret, ele muchie) {
	ret_rad = parinte[b] = a;
	ret_sum[a] = ret_sum[a] + ret_sum[b] + pret;
	ret_muchii[ret_length ++] = muchie;
}

int find_radacina (int nod) {
	if (parinte[nod] == nod)
		return nod;
	return parinte[nod] = find_radacina(parinte[nod]);
}

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)
		parinte[i] = i;

	for (const auto &p: muchii) {
		for (auto [de, la]: p.second) {
			int rada = find_radacina(de);
			int radb = find_radacina(la);
			if (rada == radb)
				continue;
			join(rada, radb, p.first, {de + 1, la + 1});
		}
	}

	/*
	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[ret_rad]);

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

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