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

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

long compconex[400000], newNrMuchii, maxCost;

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

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

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, "%ld%ld%ld", &muchii[i].varf1, &muchii[i].varf2, &muchii[i].cost);
	}
	for (i = 1;i <= x;++i)
	{
		compconex[i] = i;
	}
	std::sort(muchii + 1, muchii + y + 1, compare);
	for (i = 1;i <= y;++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, "%ld\n%ld\n", maxCost, newNrMuchii);
	for (i = 1;i <= newNrMuchii;++i)
	{
		fprintf(fout, "%ld %ld\n", newArb[i].varf1, newArb[i].varf2);
	}
	fclose(fp);
	return 0;
}