#include <stdio.h>
#define dim 20000

struct muchie{
int n1,n2,val;
};

int n,m,cost,g[dim],h[dim];
muchie t,a[2*dim];

void cit()
{
int i,j,poz;
freopen ("apm.in","r",stdin);
scanf("%d %d",&n,&m);
for (i=0;i<m;i++)
{
	scanf("%d %d %d",&a[i].n1,&a[i].n2,&a[i].val);
	a[i].n1-=1;
	a[i].n2-=1;
	// sortare
	poz=i;
	for (j=0;j<i;j++)
	{
		if(a[j].val>a[i].val)
		{
			poz=j;
			j=i+1;
		}
	}
	t=a[poz];
	a[poz]=a[i];
	for (j=poz+1;j<=i;j++)
	{
		a[i]=a[j];
		a[j]=t;
		t=a[i];
	}
	// sfarsit sortare
	if (i<n)
		g[i]=i; //ini arbori
}
fclose(stdin);
}
//------------
void krushk()
{
int p=0,ct=0,ex;
while ((p<n-1)&&(ct<m))
{
	if(g[a[ct].n1]!=g[a[ct].n2])
	{
		cost=cost+a[ct].val;// creste costu
		h[p]=ct;
		p++;// creste p
		ex=g[a[ct].n2];
		for (int i=0;i<n;i++)
			if (g[i]==ex)
				g[i]=g[a[ct].n1];// modific nodurile;
	}
	ct++;
}
}
//------------
void tip()
{
freopen("apm.out","w",stdout);
printf("%d\n",cost);
printf("%d\n",n-1);
for (int i=0;i<n-1;i++)
{
	printf("%d %d\n",a[h[i]].n2+1, a[h[i]].n1+1);
}
fclose(stdout);
}
//------------
int main()
{
cit();
krushk();
tip();
return 0;
}