#include <fstream>
#include <unordered_map>
#include <vector>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct much {
	int x, y, c;
};
bool sortare(much a, much b) {
	return a.c < b.c;
}
vector<much> muchi;
int n, m, rg[200002], T[200002];
pair <int, int> rez[200002];
int radacina(int a) {
	if (T[a] == a) {
		return a;
	}
	else {
		return T[a] = radacina(T[a]);
	}
}
int main()
{
	cin >> n >> m;
	muchi.push_back({ 0,0,0 });
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		muchi.push_back({ x, y, z });
	}
	for (int i = 1; i <= m; i++) {
		for (int j = i + 1; j <= m; j++) {
			if (muchi[i].c > muchi[j].c) {
				swap(muchi[i], muchi[j]);
			}
		}
	}
	int s = 0;
	for (int i = 1; i <= n; i++) {
		T[i] = i;
		rg[i] = 1;
	}
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		int int1, int2;
		int1 = radacina(muchi[i].x);
		int2 = radacina(muchi[i].y);
		if (int1 != int2) {
			if (rg[int1] > rg[int2]) {
				T[int2] = T[int1];
			}
			if (rg[int1] < rg[int2]) {
				T[int1] = T[int2];
			}
			if (rg[int1] == rg[int2]) {
				rg[int1]++;
				T[int1] = T[int2];
			}
			cnt++;
			rez[cnt] = make_pair(muchi[i].x, muchi[i].y);
			s = s + muchi[i].c;
		}
	}
	cout << s << '\n' << n - 1 << '\n';
	for (int i = 1; i <= cnt; i++) {
		cout << rez[i].first << ' ' << rez[i].second << '\n';
	}
}