#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
using namespace std;

struct Muchie
{
	int start;
	int end;
	int cost;		// poate float
};

int nrNoduri, nrMuchii, nrMuchiiInApm, arboreNodStart, arboreNodFinal;
long long costApm;
Muchie muchii[400005];
int arborii[200005];
Muchie muchiiInApm[400005];

void citire()
{
	scanf("%d%d", &nrNoduri, &nrMuchii);
	for(int i = 0; i < nrMuchii; ++i)
	{
		scanf("%d%d%d", &muchii[i].start, &muchii[i].end, &muchii[i].cost);
	}

	// sortam muchiile
	Muchie aux;
	for(int i = 0; i < nrMuchii-1; ++i)
		for(int j = i+1; j < nrMuchii; ++j)
		{
			if(muchii[i].cost > muchii[j].cost)
			{
				aux = muchii[i];
				muchii[i] = muchii[j];
				muchii[j] = aux;
			}
		}
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	costApm = 0;

	citire();

	// initial fiecare nod e intr-un arbore distinct
	for(int i = 0; i < nrNoduri; ++i)
		arborii[i] = i;

	// nr de muchii initial in apm e 0
	nrMuchiiInApm = 0;

	// iterator pt parcurgerea muchiilor
	int i = 0;

	// nr maxim de muchii in apm este nrNoduri - 1
	while(nrMuchiiInApm < nrNoduri - 1)
	{
		// capetele muchiilor se afla in arbori diferiti
		if(arborii[muchii[i].start] != arborii[muchii[i].end])
		{
			muchiiInApm[nrMuchiiInApm] = muchii[i];

			nrMuchiiInApm++;

			arboreNodStart = arborii[muchii[i].start];
			arboreNodFinal = arborii[muchii[i].end];

			costApm += muchii[i].cost;

			// parcurgem arborii si mutam arboreleNodFinal in arboreleNodStart
			for(int j = 0; j < nrNoduri; ++j)
			{
				if(arborii[j] == arboreNodFinal)
					arborii[j] = arboreNodStart;
			}
		}
		// trecem la urmatoarea muchie
		i++;
	}

	printf("%lld\n%d\n", costApm, nrMuchiiInApm);

	// afisam muchiile din apm
	for(int i = 0; i < nrMuchiiInApm; ++i)
	{
		printf("%d %d\n", muchii[i].start, muchii[i].end);
	}

	return 0;
}