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

Edge edge[400010];
int A[400010], conex[400010];
int myComp(const void* a, const void* b)
{
	Edge* a1 = (Edge*)a;
	Edge* b1 = (Edge*)b;
	return a1->weight > b1->weight;
}

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() {
	qsort(edge, n, sizeof(edge[0]), myComp);

}

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;
	}
		
}