#include <fstream>
#include <algorithm>
#define NMAX 200000
#define MMAX 400000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, cnt, sum, t[NMAX];
bool viz[MMAX];
struct muchie {
	int x, y, c;
} v[MMAX];

bool cmp(const muchie &a, const muchie &b) {
	return a.c < b.c;
}

int root(int x) {
	while (t[x] > 0)
		x = t[x];
	return x;
}

int main() {
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
		fin >> v[i].x >> v[i].y >> v[i].c;
	sort(v + 1, v + m + 1, cmp);
	for (int i = 1; i <= n; i++)
		t[i] = -1;
	int i = 1;
	while (cnt < n - 1) {
		int rx = root(v[i].x);
		int ry = root(v[i].y);
		if (rx != ry) {
			if (-t[rx] > -t[ry]) {
				t[rx] += t[ry];
				t[ry] = rx;
			}
			else {
				t[ry] += t[rx];
				t[rx] = ry;
			}
			cnt++;
			sum += v[i].c;
			viz[i] = true;
		}
		i++;
	}
	fout << sum << "\n" << cnt << "\n";
	for (int i = 1; i <= m; i++)
		if (viz[i])
			fout << v[i].x << " " << v[i].y << "\n";
	return 0;
}