#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, t[200005], cost;

struct muchie
{
	int x, y, c;
};
vector <muchie> apm, v;

int cmp(struct muchie x, struct muchie y)
{
	return x.c < y.c;
}

int tata(int x)
{
	while (x != t[x]) x = t[x];
	return x;
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);

	int i, x, y;
	muchie aux;

	scanf("%d %d",&N,&M);
	for (i = 1; i <= M; i++)
	{
		scanf("%d %d %d",&aux.x, &aux.y, &aux.c);
		v.push_back(aux);
	}
	for (i = 1; i <= N; i++) t[i] = i;

	sort(v.begin(), v.end(), cmp);

	for (i = 0; i < M; i++)
	{
		x = tata(v[i].x); y = tata(v[i].y);
		if (x != y)
		{
			cost += v[i].c;
			t[ x ] = y;
			apm.push_back(v[i]);
		}
	}

	printf("%d\n%d\n", cost, N - 1);
	for(i = 0; i < N - 1; i++) printf("%d %d\n", apm[i].x, apm[i].y);
	return 0;
}