#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 grupa(int i)
{
    if (P[i] == i) return i;
    P[i] = grupa(P[i]);
    return P[i];
}
 
void reuniune(int i,int j)
{
    P[grupa(i)] = grupa(j);
}

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 <= N; ++i)
		P[i] = i;
	i = 1;
	int count = 0;
	while (count < N - 1) {
		if (grupa(v[i].x) != grupa(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;*/
			reuniune(v[i].x,v[i].y);
		}
		++i;
	}
	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;
}