#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int a, b;
	int cost;
} Edge;

int costCmp(const void *a, const void *b) {
	return ( (Edge*)a )->cost - ( (Edge*)b )->cost;
}

int *Set;

int setFind(int i) {
	if (Set[i] < 0)
		return i;
	Set[i] = setFind(Set[i]);
	return Set[i];
}

void setUnion(int i, int j) {
	i = setFind(i); j = setFind(j);
	if (Set[i] < Set[j]) { // i are mai multe noduri decat j => il adaug pe j lui i
		Set[i] += Set[j];
		Set[j] = i;
	} else {
		Set[j] += Set[i];
		Set[i] = j;
	}
}

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	Edge *E;
	int n, m;
	
	scanf("%d%d", &n, &m);
	E = (Edge*)calloc(2 * m, sizeof(Edge));
	int i;
	for (i = 0; i < m; ++ i) {
		scanf("%d%d%d", &E[i].a, &E[i].b, &E[i].cost);
		-- E[i].a, -- E[i].b;
	}

	Set = (int*)calloc(n, sizeof(int));
	for (i = 0; i < n; ++ i)
		Set[i] = -1;
	qsort(E, m, sizeof(Edge), costCmp);

	int *Disp = (int*)calloc(m, sizeof(int)), cost = 0, numDisp = 0;

	int ra, rb;
	for (i = 0; i < m; ++ i) {
		ra = setFind(E[i].a); rb = setFind(E[i].b);
		if (ra != rb) {
			setUnion(ra, rb);
			Disp[numDisp ++] = i;
			cost += E[i].cost;
			//printf("%d %d %d\n", E[i].a + 1, E[i].b + 1, E[i].cost);
		}
	}

	printf("%d\n%d\n", cost, numDisp);
	for (i = 0; i < numDisp; ++ i)
		printf("%d %d\n", E[Disp[i]].a + 1, E[Disp[i]].b + 1);

	free(Disp);
	free(E);
	free(Set);
	return 0;
}