#include<stdio.h>
long a[1000][1000],s[1000];
int main()
{
	long n,m,i,j,x,y,c,min,nr=0,cost=0,k,t[1000];
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=2;i<=n;i++)
		s[i]=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j)
			{
				a[i][j]=100001;
				a[j][i]=100001;
			}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		a[x][y]=c;
		a[y][x]=c;
	}
	for(k=1;k<=n-1;k++)
	{
		min=100001;
		for(i=1;i<=n;i++)
			if(s[i])
				if(a[s[i]][i]<min)
				{
					min=a[s[i]][i];
					j=i;
				}
		t[j]=s[j];
		if(t[j]!=0)
		{	
			nr++;
			cost=cost+a[j][s[j]];
		}
		s[j]=0;
		for(i=1;i<=n;i++)
			if(s[i]&&a[i][s[i]]>a[i][j])
					s[i]=j;
		
	}
	printf("%d\n%d\n",cost,nr);
	for(i=2;i<=n;i++)
		if(t[i]!=0)
			printf("%d %d\n",t[i],i);
	return 0;
}