#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct Muchie {
	int nod1, nod2, cost;
};
bool cmp(Muchie x, Muchie y) {
	if (x.cost < y.cost)	return 1;
	return 0;
}
int main()
{
	int n, m, cost = 0;
	f >> n >> m;

	vector < Muchie > Graph(m+1), Sol;
	vector <int> comp(n + 1);
	vector <vector< int > > L(n + 1);

	for (int i = 1; i <= n; i++) {
		comp[i] = i;
		L[i].push_back(i);
	}

	for (int i = 1; i <= m; i++) {
		Muchie M;
		f >> M.nod1 >> M.nod2 >> M.cost;
		Graph[i] = M;
	}
	sort(Graph.begin()+1, Graph.end(), cmp);

	for (int i = 1; i <= m; i++) {
		
		Muchie M = Graph[i];
		if (comp[M.nod1] != comp[M.nod2]) {
			cost += M.cost;
			Sol.push_back(M);
			int elem1 = comp[M.nod1], elem2=comp[M.nod2];
			if (L[elem1].size() < L[elem2].size()) {
				auto cx = L[elem1].begin(), cy = L[elem1].end();
				for (auto i = cx; i != cy; i++) {
					comp[*i] = comp[elem2];
					L[comp[elem2]].push_back((*i));
				}
			}
			else {
				auto cx = L[elem2].begin(), cy = L[elem2].end();
				for (auto i = cx; i != cy; i++) {
					comp[*i] = comp[elem1];
					L[comp[elem1]].push_back((*i));
				}
			}
		}
	}
	g << cost << '\n' << n - 1 << '\n';
	for (auto i : Sol) {
		g << i.nod1 << ' ' << i.nod2 << ' ' << '\n';
	}

}