#include <stdio.h>
const long NMAX=200010;
const long MMAX=400010;

struct graf  {long x, y, c;};

graf g[MMAX];
long n, m, comp[NMAX], sol[MMAX], suma, nrsol;

long part(long jos, long sus);
void quicksort(long jos, long sus);

int main()
{
	long i, j, temp;
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%ld%ld", &n, &m);
	for (i=0; i<m; i++)
	  scanf("%ld%ld%ld", &g[i].x, &g[i].y, &g[i].c);
	quicksort(0, m-1);
	for (i=1; i<=n; i++)
		comp[i]=i;
	for (i=0; i<m; i++)
	{
		if (comp[g[i].x]!=comp[g[i].y])
		{
			temp=comp[g[i].y];
			for (j=1; j<=n; j++)
				if (comp[j]==temp)
					comp[j]=comp[g[i].x];
			sol[nrsol++]=i;
			suma+=g[i].c;
		}//if
	}//for i
	printf("%ld\n%ld\n", suma, nrsol);
	for (i=0; i<nrsol; i++)
		printf("%ld %ld\n", g[sol[i]].x, g[sol[i]].y);
	return 0;
}//main

long part(long jos, long sus)
{
	long p=jos, u=sus;
  graf t;
	while (p<u)
	{
		while ((g[p].c<=g[jos].c)&&(p<=u))
			p++;
		while ((g[u].c>g[jos].c)&&(p<=u))
			u--;
		if (p<u)
		{
    	t=g[p];
		  g[p]=g[u];
		  g[u]=t;
		}//if
	}//while
	t=g[jos];
	g[jos]=g[u];
	g[u]=t;
	return u;
}//part

void quicksort(long jos, long sus)
{
	long p;
	if (jos<sus)
	{
	  p=part(jos, sus);
		quicksort(jos, p-1);
		quicksort(p+1, sus);
	}//if
}//quicksort