#include <stdio.h>
#include <string.h>
#define MARE 3000
FILE *f=fopen("apm.in", "r"), *g=fopen("apm.out", "w");
long n, m, i, j, cost, a, b, k, min, h;
long c[2005][2005];
bool check[2005];

typedef struct sare
{
	int x, y;
};

sare v[101];

void citeste(void)
{
	fscanf(f, "%ld%ld", &n, &m);
	for (i=1;i<=m;i++)
	{
		fscanf(f, "%ld%ld%d", &a, &b, &k);
		c[a][b]=c[b][a]=k;
	}
}

void initializeaza(void)
{
	min=MARE;
	for (i=1;i<n;i++)
		for (j=i+1;j<=n;j++)
			if (c[i][j]<min)
			{
				min=c[i][j];
				a=i;
				b=j;
			}
	cost=min;
	k=1;
	v[k].x=i;
	v[k].y=j;
	check[a]=check[b]=1;
	c[a][b]=c[b][a]=MARE;
}

void prim(void)
{
	for (h=1;h<=n-2;h++)
	{
		min=MARE;
		for (i=1;i<n;i++)
			for (j=i+1;j<=n;j++)
				if (min>c[i][j])
					if ((!check[i]&&check[j])||(check[i]&&!check[j]))
					{
						min=c[i][j];
						a=i;
						b=j;
					}
		check[a]=check[b]=1;
		c[a][b]=c[b][a]=MARE;
		v[++k].x=a;
		v[k].y=b;
		cost+=min;
	}
}

void tipareste(void)
{
	fprintf(g, "%ld\n%ld\n", cost, k);
	for (i=1;i<=k;i++)
		fprintf(g, "%d %d\n", v[i].x, v[i].y);
}

int main(void)
{
	//memset(c, MARE, sizeof(c));
	for (i=1;i<=2000;i++)
		for (j=1;j<=2000;j++)
			c[i][j]=MARE;
	citeste();
	initializeaza();
	prim();
	tipareste();
	return 0;
}