#include <cstdio>
#include <cassert>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
#define _submit
#ifdef _submit
#define InFile "apm.in"
#define OtFile "apm.out"
#else
#define InFile "fis.in"
#define OtFile "fis.out"
#endif

typedef pair<int, int> edge;

#define MAXN 200010
#define MAXM 400010

int parinti[MAXN];
int H[MAXN];
vector<edge> rezultat;
int rezSum = 0;

void reuniune(int x, int y) {
	int mx = x, tx = x;
	while (parinti[mx] != -1)
		mx = parinti[mx];
	int my = y, ty = y;
	while (parinti[my] != -1)
		my = parinti[my];

	if (H[my] < H[mx]) {
		H[my] = H[mx];
		parinti[my] = mx;
		my = mx;
	}
	else if (H[mx] < H[my]) {
		H[mx] = H[my];
		parinti[mx] = my;
		mx = my;
	}
	else {
		H[mx]++;
		H[my]++;
		parinti[mx] = my;
		mx = my;
	}

	while (parinti[tx] != -1) {
		int aux = parinti[tx];
		parinti[tx] = mx;
		tx = aux;
	}
	while (parinti[ty] != -1) {
		int aux = parinti[ty];
		parinti[ty] = my;
		ty = aux;
	}
}

bool aresame(int x, int y) {
	int mx = x, tx = x;
	while (parinti[mx] != -1)
		mx = parinti[mx];
	while (parinti[tx] != -1) {
		int aux = parinti[tx];
		parinti[tx] = mx;
		tx = aux;
	}

	int my = y, ty = y;
	while (parinti[my] != -1)
		my = parinti[my];
	while (parinti[ty] != -1) {
		int aux = parinti[ty];
		parinti[ty] = my;
		ty = aux;
	}

	if (mx == my)
		return true;
	return false;
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OtFile, "w", stdout));
	int N, M;
	scanf("%d%d", &N, &M);
	memset(parinti, 0xFF, N * sizeof(int));
	memset(H, 0, N * sizeof(int));
	priority_queue< pair< int, edge> > Q;
	int cost;
	edge aux;
	for (int i = 0; i < M; i++) {
		scanf("%d%d%d", &aux.first, &aux.second, &cost);
		Q.push({-cost, aux});
	}
	rezultat.reserve(MAXM);
	while (!Q.empty()) {
		pair<int, edge> P = Q.top();
		P.first = -P.first;
		Q.pop();
		if (aresame(P.second.first, P.second.second))
			continue;
		reuniune(P.second.first, P.second.second);
		rezultat.push_back(P.second);
		rezSum += P.first;
	}
	printf("%d\n%d\n", rezSum, rezultat.size());
	for (auto i = rezultat.begin(); i != rezultat.end(); ++i)
		printf("%d %d\n", i->first, i->second);
	return 0;
}