#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define NMax 200005
#define MMax 400005

using namespace std;

int n, m;
vector<int> v[NMax];
int p[NMax];

int i, a[NMax], np;
int find_(int x)
{
	np = 0;

	for (i = x; p[i] != i; i = p[i])
		a[np++] = i;
	
	for (int j = 0; j < np; j++)
		p[a[j]] = i;

	return i;
}

void union_(int x, int y)
{
	p[find_(x)] = y;
}

int c1[MMax], c2[MMax], co[MMax], o[MMax], rez[NMax], rm, sum;

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

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

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
		p[i] = i;

	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &c1[i], &c2[i], &co[i]);
		o[i] = i;
	}

	qsort(o, m, sizeof(o[0]), comp_);

	int i = 0;

	for (rm = 0; rm < n - 1; rm++)
	{
		for (; find_(c1[o[i]]) == find_(c2[o[i]]); i++);

		union_(c1[o[i]], c2[o[i]]);

		rez[rm] = o[i];
		sum += co[o[i]];
	}

	printf("%d\n%d\n", sum, n - 1);

	for (int i = 0; i < n - 1; i++)
		printf("%d %d\n", c1[rez[i]], c2[rez[i]]);
	
	return 0;
}