#include<iostream>
using namespace std;

#define NMax 51
#define MMax NMax * (NMax - 1) / 2

struct Muchie { int x, y, cost; };

int n, m, *A = NULL, *c = NULL;

Muchie *G = NULL;

int compara_muchii(const void *a, const void *b)
{
	const Muchie *x = (const Muchie *)a;
	const Muchie *y = (const Muchie *)b;
	
	return x -> cost < y -> cost;
}

void citire()
{
	FILE *f = fopen("apm.in", "r");
	fscanf(f, "%d %d", &n, &m);
	
	G = (Muchie *)realloc(G, sizeof(Muchie) * (m + 1));
	A = (int *)realloc(A, sizeof(int) * (n + 1));
	c = (int *)realloc(c, sizeof(int) * (n + 1));
	
	for(int i=1; i <= m; i++)
		fscanf(f, "%d %d %d", &G[i].x, &G[i].y, &G[i].cost);
	
	for(int i=1; i <= n; i++)
		c[i] = i;
	
	fclose(f);
}

void afisare_muchii()
{
	for(int i=1; i <= m; i++)
		printf("Muchia dintre %d si %d are costul: %d \n", G[i].x, G[i].y, G[i].cost);
	
	printf("\n");
}

void afisare()
{
	FILE *fout = fopen("apm.out", "w");
	
	int CostAPM = 0;
	//printf("Arborele partial de cost minim este: \n");
	
	for(int i = 1; i < n; i++)
	{
		//printf("[%d, %d] cost = %d \n", G[A[i]].x, G[A[i]].y, G[A[i]].cost);
		CostAPM += G[A[i]].cost;
	}
	
	//printf("Costul APM = %d \n\n", CostAPM);
	fprintf(fout, "%d\n%d\n", CostAPM, n - 1);
	
	for(int i = 1; i < n; i++)
	{
		fprintf(fout, "%d %d\n", G[A[i]].y, G[A[i]].x);
	}
	
	fclose(fout);
}

void sortareMuchii(int st, int dr)
{
	int i, j;
	Muchie x;
	if(st < dr)
	{
		x = G[st]; i = st; j = dr;
		while(i < j)
		{
			while(i < j && G[j].cost >= x.cost) j--;
			G[i] = G[j];
			while(i < j && G[i].cost <= x.cost) i++;
			G[j] = G[i];
		}
		G[i] = x;
		sortareMuchii(st, i-1);
		sortareMuchii(i + 1, dr);
	}
}

int main()
{
	citire();
	//afisare_muchii();
	
	sortareMuchii(1, m);
	//qsort(G, m + 1, sizeof(Muchie), compara_muchii);
	
	int NrMSel = 0, min, max;
	
	for(int i=1; NrMSel < n - 1; i++)
		if(c[G[i].x] != c[G[i].y]) //muchia nu formeaza cicluri cu cele deaja selectate
		{
			A[++NrMSel] = i;
			
			if(c[G[i].x] < c[G[i].y])
				min = c[G[i].x], max = c[G[i].y];
			else
				min = c[G[i].y], max = c[G[i].x];
			
			for(int j=1; j <= n; j++)
				if(c[j] == max)
					c[j] = min;
		}
		
	afisare();
	
	//system("pause");
	return 0;
}