//1 Kruskal

#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

int tata[NMAX + 1];
int inaltime[NMAX + 1];

//functie de initializare
void init(int n) {
	for (int i = 1; i <= n; i++) {
		tata[i] = i;
		inaltime[i] = 0;
	}
}

//functie de gasire reprezentant
int find(int x) {
	if (tata[x] != x) {
		tata[x] = find(tata[x]);
	}
	return tata[x];
}

//functie de unire a doua componente
void unire(int x, int y) {
	int rx = find(x);
	int ry = find(y);

	if (rx != ry) {
		if (inaltime[rx] > inaltime[ry]) {
			tata[ry] = rx;
		}
		else if (inaltime[rx] < inaltime[ry]) {
			tata[rx] = ry;
		}
		else {
			tata[ry] = rx;
			inaltime[rx]++;
		}
	}
}

int main()
{
	ifstream in("apm.in");
	ofstream out("apm.out");


	int n, m;
	in >> n >> m;

	vector <tuple<int, int, int>> muchii;

	for (int i = 0; i < m; i++ ) {
		int u, v, cost;
		in >> u >> v >> cost;
		muchii.emplace_back(cost, u, v);
	}

	sort(muchii.begin(), muchii.end());

	init(n);

	int apm_cost = 0;
	vector<pair<int, int>> apm_muchii;

	//Kruskal
	for (auto [cost, u, v] : muchii) {
		if (find(u) != find(v)) {
			unire(u, v);          
			apm_cost += cost;
			apm_muchii.emplace_back(u, v); 
		}
	}

	out << apm_cost << endl;
	out << apm_muchii.size()<< endl;
	for (auto [u, v] : apm_muchii) {
		cout << u << " " << v << endl;
	}

	in.close();
	out.close();

	return 0;

}