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

#define DIMM 400002
#define DIMN 200002

using namespace std;

struct muchie {
	int x;
	int y;
	int c;
};

muchie V[DIMM];

int T[DIMN], S[DIMN], N, M, i, rx, ry, k, cost, nr;

int rad(int x) {
	while (T[x] > 0)
		x = T[x];
	return x;
}

int cmp (muchie a, muchie b) {
	return a.c < b.c;
}

int main() {
	FILE *f = fopen("apm.in","r");
	FILE *g = fopen("apm.out","w");
	fscanf(f,"%d %d",&N, &M);
	for (i=1;i<=M;i++) {
		fscanf(f,"%d %d %d",&V[i].x, &V[i].y, &V[i].c);
	}
	
	sort(V+1, V+M+1, cmp);
	for (i=1;i<=N;i++)
		T[i] = -1;
	for (i=1;i<=M;i++) {
		rx = rad(V[i].x);
		ry = rad(V[i].y);
		if (rx != ry) {
			cost += V[i].c;
			S[++k] = i;
			if (T[rx] < T[ry]) {
				T[rx] += T[ry];
				T[ry] = rx;
			} else {
				T[ry] += T[rx];
				T[rx] = ry;
			}
			nr++;
			if (nr == N-1)
				break;
		}
	}
	
	fclose(f);
	fprintf(g,"%d\n%d\n",cost,N-1);
	for (i=1;i<N;i++)
		fprintf(g,"%d %d\n",V[S[i]].x, V[S[i]].y);
		
	
	return 0;
}