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

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

long compconex[400000], newNrMuchii, maxCost;

void randomquick(struct muchie muchii[400000], int first, int last) {
	struct muchie tmp;
	int i = first, j = last, pivot;
	pivot = muchii[first + rand() % (first + last + 1)].cost;
	while (i <= j)
	{
		while (muchii[i].cost < pivot)
			i++;
		while (muchii[j].cost > pivot)
			j--;
		if (i <= j)
		{
			tmp = muchii[i];
			muchii[i++] = muchii[j];
			muchii[j--] = tmp;
		}
	}
	if (first < j)
		randomquick(muchii, first, j);
	if (last>i)
		randomquick(muchii, i, last);

}

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

int main()
{
	FILE *fp = fopen("apm.in", "r");
	FILE *fout = fopen("apm.out", "w");
	long i;
	int x, y;
	fscanf(fp, "%d%d", &x, &y);
	for (i = 1;i <= y;++i)
	{
		fscanf(fp, "%d%d%d", &muchii[i].varf1, &muchii[i].varf2, &muchii[i].cost);
	}
	for (i = 1;i <= x;++i)
	{
		compconex[i] = i;
	}
	srand(time(0)*clock());
	randomquick(muchii, 1, y);
	
	for (i = 1;i <= y && newNrMuchii<x-1;++i)
	{
		if (find_set(muchii[i].varf1) != find_set(muchii[i].varf2))
		{
			maxCost += muchii[i].cost;
			compconex[find_set(muchii[i].varf1)] = find_set(muchii[i].varf2);
			newNrMuchii++;
			newArb[newNrMuchii] = muchii[i];
		}
	}
	fprintf(fout, "%d\n%d\n", maxCost, newNrMuchii);
	for (i = 1;i <= newNrMuchii;++i)
	{
		fprintf(fout, "%d %d\n", newArb[i].varf1, newArb[i].varf2);
	}
	fclose(fp);
	return 0;
}