#define _CRT_SECURE_NO_DEPRECATE
# include <cstdio>
# include <algorithm>
#include <ctime>

#define MAXM 400002
#define MAXN 200002
#define DIM (1 << 13)

using namespace std;

struct edge {
	int x, y, c;

	inline bool operator() (const edge& n1, const edge& n2){
		return n1.c < n2.c;
	}
} E[MAXM];

int N, M, ans, pos = DIM, len;
int T[MAXN], range[MAXN], edges[MAXN];
char buf[DIM];

inline void r_int32(int& val) {
	bool neg_sign = 0;
	val = 0;

	while (buf[pos] < '0' || buf[pos] > '9') {
		if (buf[pos] == '-') neg_sign = 1;
		if (++pos >= DIM) len = fread(buf, 1, DIM, stdin), pos = 0;
	}

	while (buf[pos] >= '0' && buf[pos] <= '9') {
		if (pos == len) break;
		val = val * 10 + buf[pos] - '0';
		if (++pos == DIM) len = fread(buf, 1, DIM, stdin), pos = 0;
	}
	if (neg_sign) val = -val;
}

inline void w_int32(int k, char end) {
	char lim[16], *s;
	s = lim + 15, *s = 0, *--s = end;
	bool neg_sign = k < 0;
	if (neg_sign) k = -k;

	do {
		*--s = k % 10 + '0';
		k /= 10;
	} while (k);
	if (neg_sign) *--s = '-';

	fputs(s, stdout);
}

inline int ROOT(int x) {
	int root = x, aux;

	for (; T[root]; root = T[root]);
	for (; T[x]; aux = T[x], T[x] = root, x = aux);

	return root;
}

inline void JOIN(int x, int y) {
	if (range[x] < range[y])
		T[x] = y;
	else {
		T[y] = x;
		if (range[x] == range[y]) ++range[x];
	}
}

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

	r_int32(N), r_int32(M);
	for (int i = 1; i <= M; i++) r_int32(E[i].x), r_int32(E[i].y), r_int32(E[i].c);

	sort(E + 1, E + M + 1, edge());
	
	int root1, root2;
	for (int i = 1, pos = 1; i < N;) {
		root1 = ROOT(E[pos].x), root2 = ROOT(E[pos].y);
		if (root1 == root2) { ++pos; continue; }
		
		JOIN(root1, root2);
		ans += E[pos].c;
		edges[i++] = pos;
	}
	w_int32(ans, '\n');
	w_int32(N - 1, '\n');

	for (int i = 1; i < N; ++i)
		w_int32(E[edges[i]].x, ' '), w_int32(E[edges[i]].y, '\n');

	fprintf(stderr, "%.2lf\n", (float)clock() / CLOCKS_PER_SEC);

	return 0;
}