#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int mMax = 400001, nMax = 200001;
struct edges {
	int i, j, cost;
}M[mMax], APM[mMax];
int T[nMax];
int n, m;
int s, cntAPM;
void initializare() {
	for (int i = 1; i <= n; ++i)
		T[i] = i;
}
bool comp(edges a, edges b) {
	return a.cost < b.cost;
}
int radacina(int a) {
	if (T[a] == a)
		return a;
	else
		return T[a] = radacina(T[a]);
}
void leaga(int a, int b) {
	T[a] = T[b];
}
void kruskal() {
	int R1, R2;
	for (int i = 1; i <= m; ++i) {
		R1 = radacina(M[i].i);
		R2 = radacina(M[i].j);
		if (R1 != R2) {
			leaga(R1, R2);
			s += M[i].cost;
			APM[++cntAPM] = M[i];
		}
	}
}
int main() {
	f >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y, z;
		f >> x >> y >> z;
		M[i].i = x;
		M[i].j = y;
		M[i].cost = z;
	}
	initializare();
	sort(M + 1, M + m + 1, comp);
	kruskal();
	g << s << '\n' << n - 1 << '\n';
	for (int i = 1; i <= n - 1; ++i) {
		g << APM[i].i << " " << APM[i].j << '\n';
	}
	return 0;
}