# include <stdio.h>
# include <string.h>
using namespace std;
struct {int x; int y;} q[1600];
int a[900][900],t[900],d[900],min,x,n,i,use[900],cost,nod,m,y,z,n1,j;
void prim(int x)
{
    memset(t,0,sizeof(t));
    memset(use,0,sizeof(use));
	for (i=1; i<=n; i++)
		{ d[i]=a[x][i]; t[i]=x; }
	use[x]=1;
	while (1)
	{
		min=100000;
		nod=-1;
		for (i=1; i<=n; i++)
			if (!use[i] && min>d[i]) 
			{min=d[i]; nod=i;}
		if (min==100000) break;
		use[nod]=1;
		cost+=d[nod];
		n1++;
		q[n1].x=t[nod]; q[n1].y=nod;
		for (i=1; i<=n; i++)
			if (d[i]>a[nod][i])
			{
				d[i]=a[nod][i];
				t[i]=nod;
			}
	}
    printf("%d\n",cost);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			a[i][j]=10000;
	for (i=1; i<=m; i++)
	{
		scanf("%d %d %d",&x,&y,&z);
		a[x][y]=z;
		a[y][x]=z;
	}
	prim(1);
	printf("%d\n",n1);
	for (i=1; i<=n1; i++)
		printf("%d %d\n",q[i].x,q[i].y);
	return 0;
}