#include <fstream>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct Muchie { int x,y,c; } u[400001];
int N,M,arc[200001],L[200001];

int main ()
{
	int i, j;
	in >> N >> M;
	for (i=1; i<=M; i++)
		in >> u[i].x >> u[i].y >> u[i].c;
	in.close();
	int k=1;
	Muchie aux;
	for (i=1; i<M; i++)
		for (j=i+1; j<=M; j++)
			if (u[i].c > u[j].c) {
				aux = u[i];
				u[i] = u[j];
				u[j] = aux;
			}
	for (i=1; i<=N; i++) L[i] = i;
	i=1;
	long long cost = 0;
	while (k < N) {
		if (L[u[i].x] != L[u[i].y]) {
			int a=L[u[i].x], b=L[u[i].y];
			arc[k] = i;
			cost += u[i].c;
			for (j=1; j<=N; j++)
				if (L[j] == b) L[j] = a;
			k++;
		}
		i++;
	}

	out << cost << '\n';
	out << N-1 << '\n';
	for (i=1; i<N; i++) out << u[arc[i]].x << ' ' << u[arc[i]].y << '\n';
	out.close();
	return 0;
}