#include<stdio.h>
#include<algorithm>

using namespace std;

struct muchii {
	int x, y, c;
};

bool sort_type (muchii a, muchii b) {
    return a.c < b.c;
}

muchii v[400000], sol[200000];
int P[200000];

int N, M, i, ct = 0, j, a, b;

int main() {
	freopen ("apm.in", "r", stdin);
	freopen ("apm.out", "w", stdout);
	scanf ("%d %d", &N, &M);
	for (i = 1; i <= M; ++i)
		scanf ("%d %d %d", &v[i].x, &v[i].y, &v[i].c);
	sort(v + 1, v + M + 1, sort_type);
	//for (i = 1; i <= M; ++i) printf ("%d %d %d\n", v[i].x, v[i].y, v[i].c);
	for (i = 1; i <= N; ++i)
		P[i] = i;
	i = 1;
	int count = 0;
	while (count < N - 1) {
		if (P[v[i].x] != P[v[i].y]) {
			++count;
			sol[count].x = v[i].x;
			sol[count].y = v[i].y;
			sol[count].c = v[i].c;
			ct += v[i].c;
			a = P[v[i].y];
			b = P[v[i].x];
			for (j = 1; j <= N; ++j)
				if (P[j] == a)
					P[j] = b;
		}
		++i;
	}
	//for (i = 1; i <= N - 1; ++i) 
	//	ct += sol[i].c;
	printf ("%d\n%d\n", ct, count);
	for (i = 1; i <= count; ++i)
		printf ("%d %d\n", sol[i].x, sol[i].y);
	return 0;
}