#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define mmax 400100
#define nmax 200100
using namespace std;

int N, M, X[mmax], Y[mmax], cost[mmax];
int tati[nmax], sortat[mmax], grad[nmax], cst;
vector <int> apm;
int find(int nod) {
	if (tati[nod] == nod)
		return nod;
	else return find(tati[nod]);
}

void reuniune(int x, int y) {
	int tx = find(x);
	int ty = find(y);
	if (grad[tx] < grad[ty]) {
		tati[tx] = ty;
		grad[ty] += grad[tx];
	}
	else {
		tati[ty] = tx;
		grad[tx] += grad[ty];
	}
}

int cmp(const void * a, const void * b) {
	return (cost[*(int *)a] - cost[*(int *)b]);
}

int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	f >> N >> M;
	for (int i = 1; i <= N; ++i) {
		tati[i] = i;
		grad[i] = 1;
	}
	for (int i = 1; i <= M; ++i) {
		int x, y, c;
		f >> x >> y >> c;
		X[i] = x;
		Y[i] = y;
		cost[i] = c;
		sortat[i] = i;
	}
	qsort(sortat + 1, M, sizeof(int), cmp);
	for (int i = 1; i <= M; ++i) {
		if (find(X[sortat[i]]) != find(Y[sortat[i]])) {
			cst += cost[sortat[i]];
			reuniune(X[sortat[i]], Y[sortat[i]]);
			apm.push_back(sortat[i]);
		}
	}
	g << cst << endl;
	g << apm.size() << endl;
	for (int i = 0; i < apm.size(); ++i) {
		g << X[apm[i]] << " " << Y[apm[i]] << endl;
	}
	return 0;
}