#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

typedef struct muchie {
	int a; 
	int b;
	int val;
} muchie;

int parent[200009];
int rankN[200009];
vector<muchie> muchii;

/*
gets the group representative
*/
int group(int n) {
	if (parent[n] == n) {
		return n;
	}
	parent[n] = group(parent[n]);
	return parent[n];
}

/*
unites two groups 
*/
void unite(int a, int b) {
	int p1 = group(a);
	int p2 = group(b);
	if (p1 == p2) {//already in the same group
		return;
	}
	if (rankN[p1] == rankN[p2]) {
		parent[p1] = p2; 
		rankN[p2]++;
	}
	rankN[p1] > rankN[p2] ? parent[p2] = p1 : parent[p1] = p2;
}

int main() {
	int n, m;
	fin >> n >> m;

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	int a, b, c;
	for (int i = 1; i <= m; i++) {
		fin >> a >> b >> c;
		muchii.push_back(muchie{ a, b, c });
	}

	sort(muchii.begin(), muchii.end(), [](const muchie& m1, const muchie& m2) -> bool {
		return m1.val < m2.val;
	});

	int sumT = 0;
	vector<muchie> mst;
	for (auto m : muchii) {
		if (group(m.a) != group(m.b)) {//if the current edge unites 2 different components
			sumT += m.val;
			mst.push_back(m);
			unite(m.a, m.b);
		}
	}

	fout << sumT << "\n";
	fout << mst.size() << "\n";
	for (auto m : mst) {
		fout << m.a << " " << m.b << " " << "\n";
	}
}