#include <fstream>
#include <algorithm>

using namespace std;

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

const int N = 200001;

struct nod{
	int i, j, c;
} M[N], a[N];

int n, m, ans = 0, cnt;
int r[N];

void init() {
	for (int i = 1; i <= n; i++) {
		r[i] = 1;
	}
}

void read() {
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		in >> M[i].i >> M[i].j >> M[i].c;
	}
}

int comparare(nod a, nod b) {
	return a.c < b.c;
}

void vr(int a, int b) {
	r[a] = r[b];
}

int radacina(int a) {
	if (a == r[a]) {
		return a;
	} else return r[a] = radacina(r[a]);
}

void kruskal() {
	for (int i = 1; i <= m; i++) {
		int r1 = radacina(M[i].i);
		int r2 = radacina(M[i].j);
		if (r1 != r2) {
			ans += M[i].c;
			a[++cnt] = M[i];
			vr(r1, r2);
		}
	}
}

void output() {
	out << ans << "\n" << n - 1 << "\n";
	for (int i = 1; i < n; i++) {
		out << a[i].i << " " << a[i].j << "\n";
	}
}

int main() {
	read();
	sort(M + 1, M + m + 1, comparare);
	init();
	kruskal();
	output();
	return 0;
}