#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct muchie {
	int c, x,y;
};
vector <muchie> l;
vector <muchie> rez;
int n, m, x, y, cost, t[200001], h[200001];
void init(int v) {
	t[v] = h[v] = 0;
}
int reprez(int v) {
	if (t[v] == 0) return v;
	t[v] = reprez(t[v]);
	return t[v];
}
void reun(int u, int v) {
	int ru, rv;
	ru = reprez(u);
	rv = reprez(v);
	if (h[ru] > h[rv]) {
		t[rv] = ru;
	}
	else {
		t[ru] = rv;
		if (h[ru] == h[rv]) h[rv]++;
	}
}
bool sf(muchie m1, muchie m2) {
	return m1.c < m2.c;
}
void citire() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y >> cost;
		muchie m;
		m.c = cost;
		m.y = y;
		m.x = x;
		l.push_back(m);
	}
}
int main() {
	int s = 0;
	citire();
	sort(l.begin(), l.begin() + m, sf);
	for (int i = 0; i < m; i++) init(i);
	for (int i = 0; i < m; i++) {
		if (reprez(l[i].x) == reprez(l[i].y)) continue;
		else {
			s += l[i].c;
			rez.push_back(l[i]);
			reun(l[i].x, l[i].y);
		}
	}
	cout << s << '\n';
	cout << rez.size() << '\n';
	for (int i = 0; i < rez.size(); i++) {
		cout << rez[i].x << ' ' << rez[i].y << '\n';
	}
	return 0;
}