#include <stdio.h>
const int INF=1010;
const int NMAX=20010;
int c[NMAX][NMAX], t1, min;
long x, y, t, n, m, sel[NMAX], i, j, k, cont, apm1[NMAX], apm2[NMAX];
long cost;

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%ld%ld", &n, &m);
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			if (i!=j)
				c[i][j]=INF;
	for (i=0; i<m; i++)
	{
		scanf("%ld%ld%d", &x, &y, &t1);
		c[x][y]=t1;
		c[y][x]=t1;
	}//for i
	sel[1]=0;
	for (i=2; i<=n; i++)
		sel[i]=1;
	for (k=1; k<n; k++)
	{
		min=INF;
		for (i=1; i<=n; i++)
			if (sel[i] && (c[i][sel[i]]<min))
			{
				min=c[i][sel[i]];
				t=i;
			}//if
		apm1[cont]=t;
		apm2[cont]=sel[t];
		cost+=c[t][sel[t]];
		cont++;
		sel[t]=0;
		for (i=1; i<=n; i++)
		if (sel[i] && (c[i][t]<c[i][sel[i]]))
				sel[i]=t;
	}//for k
	printf("%ld\n", cost);
	printf("%ld\n", cont);
	for (i=0; i<cont; i++)
		printf("%ld %ld\n", apm1[i], apm2[i]);
	return 0;
}//main