#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

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

const int MAX = 200005;

int n, m;
Muchie v[MAX];

int tata[MAX];

int find_set(int x) {
	if (tata[x] == x)
		return x;
	return tata[x] = find_set(tata[x]);
}

void unite(int a, int b) {
	tata[find_set(a)] = find_set(b);
}

bool cmp(Muchie a, Muchie b) {
	return a.c < b.c;
}

pair<int,int> sol[MAX];

int main() {
	in >> n >> m;

	for (int i = 1; i <= n; ++i)
		tata[i] = i;

	for (int i = 1; i <= m; ++i)
		in >> v[i].x >> v[i].y >> v[i].c;

	sort(v + 1, v + m + 1, cmp);

	int cost = 0;
	int cnt = 0;

	for (int i = 1; i <= m; ++i) {
		int x = v[i].x;
		int y = v[i].y;

		if (find_set(x) != find_set(y)) {
			unite(x, y);
			cost += v[i].c;
			sol[++cnt] = {x, y};

			if (cnt == n - 1)
				break;
		}
	}

	out << cost << '\n';
	out << cnt << '\n';

	for (int i = 1; i <= cnt; ++i)
		out << sol[i].second << " " << sol[i].first << '\n';

	return 0;
}