#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 200005

FILE* fin, * fout;

struct edge {
	int x, y, c;
};

int n, m;
std::vector<edge> e;
std::vector<edge> apm;
int d[NMAX];

void compress(int x, int r) {
	while (x != r) {
		int t = d[x];
		d[x] = r;
		x = t;
	}
}

int root(int x) {
	int r = x;
	for (;r != d[r];r = d[r]);

	compress(x, r);

	return r;
}

void combine(int x, int y) {
	int r1 = root(x), r2 = root(y);

	d[r1] = r2;
}

void buildAPM() {
	for (int i = 1;i <= n;++i)
		d[i] = i;

	auto cmp = [](edge& e, edge& f) -> bool {return e.c < f.c;};

	sort(e.begin(), e.end(), cmp);

	for (auto a : e) {
		if (root(a.x) != root(a.y)) {
			apm.push_back(a);
			combine(a.x, a.y);
		}
	}

}

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

	fscanf(fin, "%i %i", &n, &m);

	while (m--) {
		int x, y, c;
		fscanf(fin, "%i %i %i", &x, &y, &c);
		e.push_back({ x,y,c });
	}

	buildAPM();

	int c = 0;

	for (auto a : apm)
		c += a.c;

	printf("%i\n%i\n", c, apm.size());

	for (auto a : apm)
		printf("%i %i\n", a.x, a.y);

	return 0;
}