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

#define MAXM 400002
#define MAXN 200002

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;
int T[MAXN], range[MAXN], edges[MAXN];

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);

	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; i++) scanf("%d%d%d", &E[i].x, &E[i].y, &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;
	}
	printf("%d\n%d\n", ans, N - 1);

	for (int i = 1; i < N; ++i)
		printf("%d %d\n", E[edges[i]].x, E[edges[i]].y);

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

	return 0;
}