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

template <class _Type>
using Vector = std::vector<_Type>;

template <class _Type1, class _Type2>
using Pair = std::pair<_Type1, _Type2>;

bool compare(const Pair<Pair<uint32_t, uint32_t>, int32_t>& a, const Pair<Pair<uint32_t, uint32_t>, int>& b)
{
	if (a.second < b.second)
		return true;

	return false;
}

class DisjointSet
{
	public:
		DisjointSet(uint32_t size);
		DisjointSet(const DisjointSet& source) : _rank(source._rank), _parent(source._parent) { }

		void link(uint32_t firstVertex, uint32_t secondVertex);
		void unionSets(uint32_t firstVertex, uint32_t secondVertex) { link(getRoot(firstVertex), getRoot(secondVertex)); }

		uint32_t getRoot(uint32_t vertex);

	private:
		Vector<uint32_t> _rank, _parent;
};

DisjointSet::DisjointSet(uint32_t size) : _rank(size + 1, 0), _parent(size + 1)
{
	for (uint32_t i = 0; i < size + 1; i++)
		_parent[i] = i;
}

void DisjointSet::link(uint32_t firstVertex, uint32_t secondVertex)
{
	if (_rank[firstVertex] < _rank[secondVertex])
		_parent[firstVertex] = secondVertex;
	else if (_rank[firstVertex] > _rank[secondVertex])
		_parent[secondVertex] = firstVertex;
	else
	{
		_parent[firstVertex] = secondVertex;
		_rank[secondVertex]++;
	}
}

uint32_t DisjointSet::getRoot(uint32_t vertex)
{
	uint32_t root = vertex;

	while (_parent[root] != root)
		root = _parent[root];

	// Path compression
	while (_parent[vertex] != vertex)
	{
		uint32_t aux = _parent[vertex];
		_parent[vertex] = root;
		vertex = aux;
		_rank[root]--;
	}

	return root;
}

class Graph
{
	protected:
		Vector<Pair<Pair<uint32_t, uint32_t>, int32_t>> edgesVector;
		uint32_t vertices, edges;

		Graph() : vertices(0), edges(0), edgesVector(0) { }
		Graph(const Graph& source) :
			vertices(source.vertices), edges(source.edges), edgesVector(source.edgesVector) { }
};

class UndirectedGraph : public Graph
{
	public:
		UndirectedGraph() : Graph() { }
		UndirectedGraph(std::ifstream& ifs);
		UndirectedGraph(const UndirectedGraph& source) : Graph(source) { }
		~UndirectedGraph() { };

		Vector<Pair<uint32_t, uint32_t>> getMinimumSpanningTree(int32_t& cost);
};

UndirectedGraph::UndirectedGraph(std::ifstream& ifs)
{
	ifs >> vertices >> edges;

	for (uint32_t i = 0; i < edges; i++)
	{
		int32_t cost;
		uint32_t x, y;
		ifs >> x >> y >> cost;
		edgesVector.push_back(std::make_pair(std::make_pair(x, y), cost));
	}
}

Vector<Pair<uint32_t, uint32_t>> UndirectedGraph::getMinimumSpanningTree(int32_t& cost)
{
	std::sort(edgesVector.begin(), edgesVector.end(), compare);

	DisjointSet disjointSet(vertices);
	Vector<Pair<uint32_t, uint32_t>> mstEdges;	// Minimum Spanning Tree edges

	for (uint32_t i = 0; i < edgesVector.size(); i++)
	{
		int32_t _cost = edgesVector[i].second;
		uint32_t x = edgesVector[i].first.first;
		uint32_t y = edgesVector[i].first.second;

		if (disjointSet.getRoot(x) != disjointSet.getRoot(y))
		{
			mstEdges.push_back(std::make_pair(x, y));
			disjointSet.unionSets(x, y);
			cost += _cost;
		}
	}

	return mstEdges;
}

int main()
{
	std::ifstream f("apm.in");
	std::ofstream g("apm.out");
	UndirectedGraph graph(f);

	int cost = 0;
	Vector<Pair<uint32_t, uint32_t>> mst = graph.getMinimumSpanningTree(cost);

	g << cost << "\n" << mst.size() << "\n";
	for (uint32_t i = 0; i < mst.size(); i++)
		g << mst[i].first << " " << mst[i].second << "\n";

	return 0;
}