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

using namespace std;

const int NMax = 400005;

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

pair<int, int>p[NMax];
int n, m, total, tt[NMax], rg[NMax], k;

struct muchie {
	int x, y, cost;
}v[NMax];

bool cmp(muchie a, muchie b) {
	return a.cost < b.cost;
}
int find(int Nod) {
	while (tt[Nod] != Nod)
		Nod = tt[Nod];
	return Nod;
}
void unire(int x,int y) {
	if (rg[x] < rg[y])
		tt[x] = y;
	if (rg[x] > rg[y])
		tt[y] = x;
	if (rg[x] == rg[y]) {
		tt[x] = y;
		rg[y]++;
	}
}
void solve() {
	for (int i = 1; i <= n; i++) {
		tt[i] = i;
		rg[i] = 1;
	}
	for (int i = 1; i <= m; i++) {
		int gasitx = find(v[i].x);
		int gasity = find(v[i].y);
		if (gasitx!=gasity) {
			unire(gasitx, gasity);
			p[++k].first = v[i].x;
			p[k].second = v[i].y;
			total += v[i].cost;
		}
	}
}
int main() {
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		fin >> v[i].x >> v[i].y >> v[i].cost;
	}
	sort(v + 1, v + m + 1, cmp);
	solve();
	fout << total << "\n";
	fout << n - 1 << "\n";
	for (int i = 1; i <= k; i++) {
		fout << p[i].first << " " << p[i].second << "\n";
	}
	return 0;
}