#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

struct Nod {
	int tata, inaltime;
	Nod() : tata(-1), inaltime(1) {}
};

struct Muchie {
	int start, end, cost;
};

Nod* graf;
Muchie* muchii;
std::vector<Muchie> muchii_apm;
int n = 0, m = 0, cost_total = 0;

int cmp_muchie(const void* a, const void* b)
{
	Muchie* pa = (Muchie*)a;
	Muchie* pb = (Muchie*)b;

	return pa->cost - pb->cost;
}

int radacina(int nod)
{
	int rad = nod;
	while(graf[rad].tata >= 0)
		rad = graf[rad].tata;

	return rad;
}

bool reuneste(Muchie muchie)
{
	int rad_start = radacina(muchie.start);
	int rad_end = radacina(muchie.end);
	bool succes = false;
	
	if(rad_start != rad_end)
	{
		if(graf[rad_start].inaltime > graf[rad_end].inaltime)
		{
			graf[rad_end].tata = rad_start;
			graf[rad_start].inaltime = std::max(graf[rad_start].inaltime, graf[rad_end].inaltime + 1);
		}
		else
		{
			graf[rad_start].tata = rad_end;
			graf[rad_end].inaltime = std::max(graf[rad_end].inaltime, graf[rad_start].inaltime + 1);
		}

		succes = true;
	}

	return succes;
}

void kruskal(int start)
{
	qsort(muchii, m, sizeof(Muchie), cmp_muchie);

	for(int i = 0; i < m && muchii_apm.size() < n - 1; i++)
	{
		if(reuneste(muchii[i]))
		{
			cost_total += muchii[i].cost;
			muchii_apm.push_back(muchii[i]);
		}
	}
}

int main()
{
	std::ifstream fin("apm.in");
	std::ofstream fout("apm.out");
	if(!fin.is_open() || !fout.is_open())
		return -1;

	int a = 0, b = 0, c = 0;
	fin >> n >> m;

	graf = new Nod[n];
	muchii = new Muchie[m];

	for(int i = 0; i < m; i++)
	{
		fin >> a >> b >> c;
		muchii[i].start = a - 1;
		muchii[i].end = b - 1;
		muchii[i].cost = c;
	}

	kruskal(0);

	fout << cost_total << '\n';
	fout << muchii_apm.size() << '\n';

	for(size_t i = 0; i < muchii_apm.size(); i++)
		fout << muchii_apm[i].start + 1 << ' ' << muchii_apm[i].end + 1 << '\n';

	delete[] graf;
	delete[] muchii;
	return 0;
}