#include <stdio.h>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

int N, M;
const int MMAX = 400005;
const int NMAX = 200005;

int set[NMAX];

typedef pair<int, int> muchie;

typedef pair<int, muchie> c_m;

vector<c_m> muchii(MMAX);

int find(int x) {
	if (x != set[x]) {
		set[x] = find(set[x]);
	}
	return set[x];
}

void union1(int x, int y) {
	int px = find(x);
	int py = find(y);

	if (px == py) {
		return;
	}

	set[px] = py;
}

int main() {
	std::ifstream in("apm.in");
	std::ofstream out("apm.out");

	in >> N >> M;

	for (int i = 1; i < N; ++i) {
		set[i] = i;
	}

	for (int i = 0; i < M; ++i) {
		int x, y, c;
		in >> x >> y >> c;
		muchii[i] = make_pair(c, make_pair(x, y));
	}

	sort(muchii.begin(), muchii.end());

	vector<muchie> sol;
	int arb_cost = 0;

	for (auto top : muchii) {
		muchie m = top.second;
		int c = top.first;

		if (find(m.first) != find(m.second)) {
			arb_cost += c;
			union1(m.first, m.second);
			sol.push_back(m);
		}
	}

	out << arb_cost << '\n' << N - 1 << '\n';


	for (int i = 0; i < N - 1; ++i) {
		out << sol[i].first << ' ' << sol[i].second << '\n';
	}

	system("PAUSE");
	return 0;
}