#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>

struct muchie{
	long varf1, varf2;
	long cost;
}muchii[400000], newArb[400000];

FILE *fout = fopen("apm.out", "w");

long compconex[400000], newNrMuchii;

int find_set(int i)
{
	while (compconex[i])
	{
		i = compconex[i];
	}

	return i;
}

void kruskal(struct muchie muchii[400000], long compconex[400000], long nrMuchii, long nrNoduri)
{
	int i;
	for (i = 1; i <= nrNoduri; i++)
	{
		compconex[i] = 0;
	}
	int set1, set2, k;
	i = 0;
	while (i <= nrMuchii && newNrMuchii < nrNoduri - 1)
	{
		set1 = find_set(muchii[i].varf1);
		set2 = find_set(muchii[i].varf2);
		if (set1 != set2)
		{
			newArb[newNrMuchii] = muchii[i];
			newNrMuchii++;
			compconex[set2] = set1;
		}
		i++;
	}
	int cost = 0;
	//printf("Kruskal:\n");

	for (i = 0; i < newNrMuchii; i++)
	{
		//printf("%d %d %d\n", newArb[i].varf1, newArb[i].varf2, newArb[i].cost);
		cost += newArb[i].cost;
	}
	fprintf(fout, "%d\n", cost);
	fprintf(fout, "%d\n", newNrMuchii);
	for (i = 0; i < newNrMuchii; i++)
	{
		fprintf(fout, "%d %d\n", newArb[i].varf2, newArb[i].varf1);
		//cost += newArb[i].cost;
	}
	//printf("Costul minim este: %d\n", cost);
}


bool compare(muchie x, muchie y)
{
	return (x.cost < y.cost);
}

int main()
{
	long nrMuchii = 0;
	FILE *fp = fopen("apm.in", "r");
	long i, nrNoduri = 0;
	int x, y;
	fscanf(fp, "%d%d", &x, &y);
	while ((fscanf(fp, "%d%d%d", &muchii[nrMuchii].varf1, &muchii[nrMuchii].varf2, &muchii[nrMuchii].cost)) != EOF)
	{
		nrMuchii++;
		if (muchii[nrMuchii - 1].varf1 > nrNoduri)
			nrNoduri = muchii[nrMuchii - 1].varf1;
		if (muchii[nrMuchii - 1].varf2 > nrNoduri)
			nrNoduri = muchii[nrMuchii - 1].varf2;
	}
	nrMuchii--;
	std::sort(muchii, muchii + nrMuchii, compare);
	/*for (i = 0; i <= nrMuchii; i++)
	{
	fprintf(stdout, "%d %d %d\n", muchii[i].varf1, muchii[i].varf2, muchii[i].cost);
	}*/
	kruskal(muchii, compconex, nrMuchii, nrNoduri);
	fclose(fp);
	return 0;
}

/*1 2 7
1 4 5
2 3 8
2 4 9
2 5 7
3 5 5
4 5 15
4 6 6
5 6 8
5 7 9
6 7 11


1 2 4
1 8 8
2 8 11
2 3 8
3 9 2
3 6 4
3 4 7
4 6 14
4 5 9
5 6 10
6 7 2
7 8 1
7 9 6
8 9 7
*/