#include <stdio.h>

const int DIMN = 200005;
struct muc { int a, b, c; } G[DIMN+DIMN], mx[DIMN+DIMN];
int T[DIMN], R[DIMN], N, M, C;

void sort_dei (muc *s, muc *d)
{
	if (d - s <= 0)
		return;
	muc *i, *j, *m = s + ((d - s) >> 1); 
	
	sort_dei (s, m);
	sort_dei (m + 1, d);
	
	for (i = s, j = m+1; i != m+1 && j != d+1;)
		if (i->c < j->c)
			mx[++mx[0].c] = *i++;
		else
			mx[++mx[0].c] = *j++;
	while (i != m+1)
		mx[++mx[0].c] = *i++;
	while (j != d+1)
		mx[++mx[0].c] = *j++;
	
	for (i = d; i != s-1; i--)
		*i = mx[mx[0].c--];
}

void init ()
{
	freopen ("apm.in", "r", stdin);
	freopen ("apm.out", "w", stdout);	
	
	scanf ("%d%d", &N, &M);
	for (int i = 0; i < M; i++)
		scanf ("%d%d%d", &G[i].a, &G[i].b, &G[i].c);
	sort_dei (G, G + M - 1);
	for (int i = 1; i <= N; i++)
		T[i] = -1;
}

int rad (int n)
{
	if (T[n] < 0) 
		return n;
	return rad (T[n]);
}

void pmd (int t, int f)
{
	T[t] += T[f]; 
	T[f] = t;
}

void rezo ()
{
	int r1, r2;
	for (int i = 0; R[0] < N - 1; i++)
	{
		r1 = rad (G[i].a);
		r2 = rad (G[i].b);
		if (r1 == r2)
			continue;
		
		R[++R[0]] = i;
		C += G[i].c;
		
		if (T[r1] < T[r2])
			pmd (r1, r2);
		else
			pmd (r2, r1);
	}
}

void afis ()
{
	printf ("%d\n%d\n", C, R[0]);
	for (int i = 1; i <= R[0]; i++)
		printf ("%d %d\n", G[R[i]].a, G[R[i]].b);
}

int main ()
{
	init ();
	rezo ();
	afis ();
	return 0;
}