#include <iostream>
#include <fstream>
#include <algorithm>
#include<vector>
#define max 200100
using namespace std;

int x[max], y[max], cost[max], tati[max];
int muchie[max], N, M, cst;
vector <int> apcm;

int findRad(int nod) {
	if (tati[nod] == nod)
		return nod;
	int tata = findRad(tati[nod]);
	return tata;
}

void reuniune(int a, int b) {
	tati[findRad(a)] = findRad(b);
}

bool cmp(int a, int b) {
	return (cost[a] < cost[b]);
}

int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	f >> N >> M;
	for (int i = 1; i <= N; ++i)
		tati[i] = i;
	for (int i = 1; i <= M; ++i)
	{
		int a, b, c;
		f >> a >> b >> c;
		x[i] = a;
		y[i] = b;
		cost[i] = c;
		muchie[i] = i;
	}
	sort(muchie, muchie + M + 1, cmp);
	for (int i = 1; i <= N; ++i) {
		if (tati[x[muchie[i]]] != tati[y[muchie[i]]]) {
			cst += cost[muchie[i]];
			reuniune(x[muchie[i]], y[muchie[i]]);
			apcm.push_back(muchie[i]);
		}
	}
	g << cst << endl;
	g << apcm.size();
	for (int i = 0; i < apcm.size(); ++i)
		g << x[apcm[i]] << " " << y[apcm[i]] << endl;
	return 0;
}