#include<stdio.h>
#define NMAX 1001
int ww[NMAX],x[NMAX][NMAX],y[NMAX][NMAX],z[NMAX],q[NMAX],i,j,n,m,k,l,a,s,b,c,nod,min,pmin;
struct kkt
{
	int X,Y;
} w[NMAX];
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		x[a][++x[a][0]]=b;
		x[b][++x[b][0]]=a;
		y[a][++y[a][0]]=c;
		y[b][++y[b][0]]=c;
	}
	for (i=1;i<=x[1][0];i++)
	{
		z[x[1][i]]=y[1][i];
		q[x[1][i]]=1;
	}
	for (i=1;i<=n;i++)
		if (q[i]!=1)
			z[i]=1001;
	k=1;
	ww[1]=1;
	while (k<n)
	{
		min=1001;
		pmin=0;
		for (i=1;i<=n;i++)
			if (z[i]<min&&!ww[i])
			{
				min=z[i];
				pmin=i;
			}
		k++;
		s+=min;
		w[k].X=pmin;
		w[k].Y=q[pmin];

		for (i=1;i<=x[pmin][0];i++)
		if (!ww[x[pmin][i]])
		{
			nod=x[pmin][i];
			if (z[nod]>y[pmin][i])
			{
				z[nod]=y[pmin][i];
				q[nod]=pmin;
			}
		}
		ww[pmin]=1;
	}
	printf("%d\n",s);
	printf("%d\n",n-1);
	for (i=2;i<=n;i++)
		printf("%d %d\n",w[i].X,w[i].Y);

	return 0;
}