#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

struct Con {
	int a;
	int b;
	int w;
};

bool cmp(Con a, Con b) {
	return(a.w < b.w);
}

int n, m;
Con con[400004];
int nod[200002];
int wgt[200002];

bool add(int a, int b) {
	while (a != nod[a]) {
		nod[a] = nod[nod[a]];
		a = nod[a];
	}
	while (b != nod[b]) {
		nod[b] = nod[nod[b]];
		b = nod[b];
	}
	if (a != b) {
		if (wgt[a] > wgt[b]) {
			wgt[a] += wgt[b];
			nod[b] = a;
		} else {
			wgt[b] += wgt[a];
			nod[a] = b;
		}
		return(1);
	}
	return(0);
}

int slv[200002];

int main() {
	FILE * in = fopen("apm.in", "rt");
	FILE * out = fopen("apm.out", "wt");

	fscanf(in, "%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		nod[i] = i;
	}
	for (int i = 1; i <= m; ++i) {
		fscanf(in, "%d%d%d", &con[i].a, &con[i].b, &con[i].w);
	}
	std::sort(con + 1, con + m + 1, cmp);

	int sum = 0;
	int count = 0;
	for (int i = 1; i <= m; ++i) {
		if (add(con[i].a, con[i].b)) {
			sum += con[i].w;
			slv[count++] = i;
		}
	}

	fprintf(out, "%d\n", sum);
	fprintf(out, "%d\n", count);
	for (int i = 0; i < count; ++i) {
		fprintf(out, "%d %d\n", con[slv[i]].a, con[slv[i]].b);
	}

	fclose(in);
	fclose(out);
}