#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

const int NMAX = 200002;
const int MMAX = 400002;

struct Muchie {
	int nod1;
	int nod2;
	int cost;
};


Muchie Muchii[MMAX];
int father[NMAX];
std::vector<Muchie> Arbore;

bool compare(Muchie A, Muchie B) {
	return A.cost < B.cost;
}

void init_fathers(int N) {
	for (int i = 1; i <= N; ++i) {
		father[i] = i;
	}
}

int findFather(int nod) {

	if (nod != father[nod]) {
		return findFather(father[nod]);
	}
	return nod;
}

int Kruskal(int N, int M) {

	int muchiiGasite = 0;
	int i = 1;
	int arbCost = 0;
	while (muchiiGasite < N - 1) {
		if (findFather(Muchii[i].nod1) != findFather(Muchii[i].nod2)) {
			arbCost += Muchii[i].cost;
			++muchiiGasite;
			Arbore.push_back(Muchii[i]);
			father[findFather(Muchii[i].nod1)] = findFather(Muchii[i].nod2);
		}
		++i;
	}

	return arbCost;
}

int main() {

	std::ifstream in("apm.in");
	std::ofstream out("apm.out");

	int N, M;
	in >> N >> M;

	for (int i = 1; i <= M; ++i) {
		in >> Muchii[i].nod1 >> Muchii[i].nod2 >> Muchii[i].cost;
	}

	std::sort(Muchii + 1, Muchii + M + 1, compare);
	init_fathers(N);
	int cost_min = Kruskal(N, M);

	out << cost_min << '\n';
	out << N - 1 << '\n';
	for (int i = 0; i < N - 1; ++i) {
		out << Arbore[i].nod1 << ' ' << Arbore[i].nod2 << '\n';
	}

	system("PAUSE");
	return 0;
}