// Kruskal
#include <stdio.h>
#define M_MAX 400000
#define N_MAX 200000

struct muchie {
	int x, y, c;
} v[M_MAX];
int uf[N_MAX + 1], buff[N_MAX];

void qsort(int beg, int end)
{
	if (end - beg > 1) {
		int piv = v[(beg * 3 + end * 5) / 8].c;
		int l = beg - 1, r = end;
		while (l < r) {
			while (v[++l].c < piv);
			while (v[--r].c > piv);
			if (l < r) {
				muchie aux = v[l];
				v[l] = v[r];
				v[r] = aux;
			}
		}
		qsort(beg, l);
		qsort(l, end);
	}
}

void inituf(int N)
{
	int i;
	for (i = 1; i <= N; i++) {
		uf[i] = i;
	}
}

int root(int node)
{
	if (uf[node] == node) {
		return node;
	} else {
		uf[node] = root(uf[node]);
		return uf[node];
	}
}

void unify(int node1, int node2)
{
	uf[node1] = root(node2);
}

int main()
{
	FILE *fin, *fout;
	fin = fopen("apm.in", "r");
	fout = fopen("apm.out", "w");

	int N, M;
	fscanf(fin, "%d%d", &N, &M);
	inituf(N);

	int i;
	for (i = 0; i < M; i++) {
		fscanf(fin, "%d%d%d", &v[i].x, &v[i].y, &v[i].c);
	}
	qsort(0, M);

	int cnt = 0, sum = 0;
	i = 0;
	while (cnt < N - 1) {
		if (root(v[i].x) != root(v[i].y)) {
			cnt ++;
			buff[cnt] = i;
			sum += v[i].c;
			unify(v[i].x, v[i].y);
		}
		i++;
	}
	fprintf(fout, "%d\n%d\n", sum, N - 1);
	for (i = 1; i < N; i++) {
		fprintf(fout, "%d %d\n", v[buff[i]].x, v[buff[i]].y);
	}

	fclose(fin);
	fclose(fout);
	return 0;
}