#include <stdio.h>
#include <stdlib.h>

#define NMAX 400010

typedef struct
{
	long x, y, c;
} muc;

muc a[NMAX];
long n, m;

void read()
{
	long i;
	scanf("%ld %ld", &n, &m);
	for(i = 1; i <= m; ++i)
		scanf("%ld %ld %ld", &a[i].x, &a[i].y, &a[i].c);
}
int cmp(const void *a, const void *b)
{
	return ( ((muc *)a) -> c ) - ( ((muc *)b) -> c );
}

long mul[NMAX];

int find(int x)
{
	if(mul[x] == x) return x;
	mul[x] = find(mul[x]);
	return mul[x];
}
void join(int x, int y)
{
	if(x&1)
		mul[x] =y;
	else
		mul[y] = x;
}

long x1[NMAX], x2[NMAX], h;



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

	read();
	qsort(a+1, m, sizeof(muc), cmp);

	//for(int i = 1; i <= m; ++i)
	//	printf("%ld %ld %ld\n", a[i].x, a[i].y, a[i].c);

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

	long sum = 0;
	for(i = 1; i <= m; ++i)
	{
		x = find(a[i].x);
		y = find(a[i].y);

		if(x != y)
		{
			join(x, y);
			sum += a[i].c;
			x1[++h] = a[i].x;
			x2[h] = a[i].y;
		}
	}
	printf("%ld\n", sum);
	printf("%ld\n", h);
	for(i = 1; i <= h; ++i)
		printf("%ld %ld\n", x1[i], x2[i]);

	return 0;
}