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

int n, m;

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

std::vector<Muchie> muchii;

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

struct Subset
{
	int parent, rank; // rank = inaltimea arborelui
};

int find(std::vector<Subset>& subsets, int i)
{
	if (subsets[i-1].parent != i)
		subsets[i-1].parent = find(subsets, subsets[i-1].parent);
	return subsets[i-1].parent;
}

void Union(std::vector<Subset>& subsets, int x, int y)
{
	int xRoot = find(subsets, x);
	int yRoot = find(subsets, y);

	if (subsets[xRoot-1].rank < subsets[yRoot-1].rank)
		subsets[xRoot-1].parent = yRoot;
	else if (subsets[xRoot-1].rank > subsets[yRoot-1].rank)
		subsets[yRoot-1].parent = xRoot;
	else
	{
		subsets[yRoot-1].parent = xRoot;
		subsets[xRoot-1].rank++;
	}
}

std::vector<Muchie> kruksalMST()
{
	std::sort(muchii.begin(), muchii.end(), compareMuchii); // sortare in ordine crescatoare

	std::vector<Subset> subsets(n);

	for (int i = 0; i < n; i++) // initializarea submultimilor
	{
		subsets[i].parent = i+1;
		subsets[i].rank = 0;
	}

	std::vector<Muchie> mst;

	for (const Muchie& muchie : muchii)
	{
		int x = find(subsets, muchie.src);
		int y = find(subsets, muchie.dest);

		if (x != y) // daca adaugand muchia nu se face ciclu se adauga la mst
		{
			mst.push_back(muchie);
			Union(subsets, x, y);
		}
	}

	return mst;

}

void initFromFile()
{
	std::ifstream fin("grafpond.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 });
	}

	fin.close();
}

void init()
{
	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 });
	}
}

std::vector<Muchie> mst;

int costMST()
{
	int cost = 0;

	for (const Muchie& muchie : mst)
	{
		cost = cost + muchie.cost;
	}

	return cost;
}

void printMuchiiMST()
{
	for (const Muchie& muchie : mst)
	{
		std::cout << muchie.src << ' ' << muchie.dest << '\n';
	}
}

int main()
{
	init();

	mst = kruksalMST();

	std::cout << costMST() << '\n';

	std::cout << mst.size() << '\n';

	printMuchiiMST();

	return 0;
}