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

int n, m, costMST;
std::vector<int> h, p;

struct Muchie
{
	int src, dest, cost;
};

std::vector<Muchie> muchii, muchiiMST;

bool compareMuchii(const Muchie& a, const Muchie& b)
{
	return a.cost < b.cost;
}

int Find(int _x)
{
	if (p[_x - 1] == 0)
	{
		return _x;
	}

	return p[_x - 1] = Find(p[_x - 1]);
}

void Union(int _x, int _y)
{
	int _a = Find(_x);
	int _b = Find(_y);
	if (_a != _b)
	{
		if (h[_a - 1] < h[_b - 1])
		{
			p[_a - 1] = _b;
		}
		else if (h[_a - 1] > h[_b - 1])
		{
			p[_b - 1] = _a;
		}
		else
		{
			p[_b - 1] = _a;
			h[_a - 1]++;
		}
	}
}

template <typename T>
void printVector(std::vector<T> vec)
{
	for (auto i : vec)
	{
		std::cout << i << ' ';
	}
	std::cout << '\n';
}

void initFromKeyboard()
{
	std::cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int _a, _b, _c;
		std::cin >> _a >> _b >> _c;
		muchii.push_back({ _a, _b, _c });
	}

	h.resize(n, 1);
	p.resize(n, 0);
	costMST = 0;
}

void initFromFile()
{
	std::ifstream fin("apm.in");
	fin >> n >> m;
	
	for (int i = 0; i < m; i++)
	{
		int _a, _b, _c;
		fin >> _a >> _b >> _c;
		muchii.push_back({ _a, _b, _c });
	}

	h.resize(n, 1);
	p.resize(n, 0);
	costMST = 0;

	fin.close();
}

void kruksalMST()
{
	std::sort(muchii.begin(), muchii.end(), compareMuchii); // sortare in ordine crescatoare

	for (auto muchie : muchii)
	{
		if (Find(muchie.src) != Find(muchie.dest))
		{
			Union(muchie.src, muchie.dest);
			costMST += muchie.cost;
			muchiiMST.push_back(muchie);
		}
	}
}

void printMSTinFile()
{
	std::ofstream fout("apm.out");
	
	fout << costMST << '\n';
	fout << muchiiMST.size() << '\n';
	for (auto muchie : muchiiMST)
	{
		fout << muchie.src << ' ' << muchie.dest << '\n';
	}

	fout.close();
}

int main()
{
	initFromFile();

	kruksalMST();

	printMSTinFile();

	return 0;
}