#include<stdio.h>
#define dim 400005
using namespace std;

int c[dim],a[dim],b[dim],n,m,i,j,comp[dim/2],ok,cost,nr;
short int mark[dim];

void sort(int in,int sf)
{int temp,aux;
	i=in;
	j=sf;
	temp=c[(i+j)/2];
	
	while(i<=j)
	{
		while(c[i] < temp) i++;
		while(c[j] > temp) j--;
		
		if(i<=j)
		{
			aux=c[i], c[i]=c[j]; c[j]=aux;
			aux=a[i], a[i]=a[j]; a[j]=aux;
			aux=b[i], b[i]=b[j]; b[j]=aux;		
		}
		if(i<=j)
			{i++;j--;}	
	}
if(in<j) sort(in,j);
if(i<sf) sort(i,sf);

}

int main()
{
	FILE *f=fopen("apm.in","r"), *g=fopen("apm.out","w");
	
fscanf(f,"%d %d",&n,&m);

for(i=1;i<=m;i++)
	fscanf(f,"%d %d %d",&a[i],&b[i],&c[i]);

sort(1,m);

cost=c[1];
mark[1]=comp[a[1]]=comp[b[1]]=1;
nr=1;

while(!ok)
{ok=1;
	
	for(i=1;i<=m;i++)
		if(!mark[i] && comp[a[i]] != comp[b[i]] )
		{
		mark[i] = 1;
		comp[a[i]] = comp[b[i]] = 1;
		cost+=c[i];
		nr++;
		ok=0;	
		break;
		}
}

fprintf(g,"%d\n%d\n",cost,nr);
for(i=1;i<=m;i++)
	if(mark[i]==1)
		fprintf(g,"%d %d\n",a[i],b[i]);
	
fclose(f);
fclose(g);
return 0;
}