#include <fstream>
using namespace std;
ifstream fin("apcm.in");
ofstream fout("apcm.out");
int n, m;
struct Edge {
	int src, dest, weight;
};

Edge edge[1000];
int A[1000], conex[1000];

void init() {
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		fin >> edge[i].src >> edge[i].dest >> edge[i].weight;
	}

	for (int i = 1; i <= n; i++)
		conex[i] = i;

}
void sortare() {

	for (int i = 1; i < m; i++) {
		for (int j = i + 1; j <= m; j++) {
			if (edge[j].weight < edge[i].weight) {
				Edge x;
				x = edge[j];
				edge[j] = edge[i];
				edge[i] = x;
			}
		}
	}

}

int main() {
	init();
	sortare();

	int nrmsel = 0;
	int min, max;

	for (int i = 1; nrmsel < n - 1; i++) {
		if (conex[edge[i].src] != conex[edge[i].dest]) {

			A[++nrmsel] = i;

			if (conex[edge[i].src] < conex[edge[i].dest]) {
				min = conex[edge[i].src];
				max = conex[edge[i].dest];
			}
			else {
				min = conex[edge[i].dest];
				max = conex[edge[i].src];
			}

			for (int j = 1; j <= n; j++) {
				if (conex[j] == max)conex[j] = min;
			}

		}
	}
	int cost = 0;
	for (int i = 1; i <= nrmsel; i++) {
		//fout << edge[A[i]].src << " " << edge[A[i]].dest << endl;
		cost += edge[A[i]].weight;
	}
	fout << cost << endl;
	fout << nrmsel << endl;
	for (int i = 1; i <= nrmsel; i++) {
		fout << edge[A[i]].src << " " << edge[A[i]].dest << endl;
	}
		
}