#include <cstdio>
#define DIM 1000

const int INF = 1<<30;
int n, m, a[DIM][DIM], V[DIM], E[2][DIM], viz[DIM], noduri, cost;

void min(int &u, int &v)
{
	int min = INF;
	for (int i = 1; i <= noduri; i++)
	{
		for (int j = 1; j <= n; j++)
			if (!viz[j])
				if (a[ V[i] ][j] < min)
				{
					u = V[i];
					v = j;
					min = a[ V[i] ][j];
				}
	}

}



int main()
{
	FILE *f = fopen("apm.in", "r");
	if (!f)
		printf ("MUIE\n");
	fscanf(f, "%d%d", &n, &m);
	int x, y,  i, j;

	for (i = 0; i <= n; i++)
		for (j = 0; j <= n; j++)
			a[i][j] = INF;

	for (i = 1; i <= m; i++)
	{
 		fscanf(f, "%d%d", &x, &y);
 		fscanf(f, "%d",  &a[x][y]);
 		a[y][x] = a[x][y];
	}

	fclose(f);
/*	for (i = 0; i <= n; i++)
	{
		for (j = 0; j <= n; j++)
			printf("%3d", a[i][j]);

		printf("\n");
	}
*/
	noduri = viz[1] = 1;
	V[1] = 1;
	int u, v;
	while( noduri != n )
	{
		min(u, v);
		V[ ++noduri ] = v;
		E[0][ noduri - 1] = u;
		E[1][ noduri - 1] = v;
		viz[v] = 1;
		cost += a[u][v];
	}

	f = fopen("apm.out", "w");
	fprintf(f, "%d\n%d\n", cost, n - 1);
	for (i = 1; i <= n - 1; i++)
 		fprintf(f, "%d %d\n", E[0][i], E[1][i]);

	fclose(f);



	return 0;
}