#include <fstream>
#include <vector>
#include <algorithm>
#include <list>
#include <unordered_map>
#include <utility>
#include <tuple>
#include <queue>
 
struct file_manip {
 
	std::ifstream fin;
	std::ofstream fout;
 
	file_manip(const char* filename) {
		std::string infilename  = std::string(filename) + ".in";
		std::string outfilename = std::string(filename) + ".out";
		fin.open(infilename.c_str());
		fout.open(outfilename.c_str());
	}
 
	template <class T>
	file_manip& operator << (const T& rhs) {
		fout << rhs;
		return *this;
	}
	template <class T>
	file_manip& operator >> (T& rhs) {
		fin >> rhs;
		return *this;
	}
};

struct DS
{
	std::vector<int, int> parent;
	const int N;
	DS(int N) : N(N)
	{
		parent.reserve(N + 1);
		for (auto x = 0; x <= N; ++x)
		{
			parent.emplace_back(x);
		}
	}

	int GetEarliestParent(int x) const
	{
		const auto p = parent.at(x);
		if (x == p) {
			return x;
		}
		return GetEarliestParent(p);
	}

	void Associate(int x, int y)
	{
		const auto s1 = GetEarliestParent(x);
		const auto s2 = GetEarliestParent(y);

		parent[s1] = s2;
	}

	bool AreTheSame(int x, int y) const
	{
		return GetEarliestParent(x) == GetEarliestParent(y);
	}

};
using Edge = std::tuple<int, int, int>;
using RegularEdge = std::pair<int, int>;
struct EdgeComparator
{
	bool operator()(const Edge& lhs, const Edge& rhs) const
	{
		return std::get<2>(lhs) > std::get<2>(rhs);
	}
};
 
int main()
{
	file_manip fm("apm");
	std::priority_queue<Edge, std::vector<Edge>, EdgeComparator> pq;
	int n, m;
	int x, y, c;
	fm >> n >> m;
	DS ds(n);
	long long sum = 0;
	std::vector<RegularEdge> solution;
	solution.reserve(n);
	while (m--)
	{
		fm >> x >> y >> c;
		pq.emplace(x,y,c);
	}
	int added = 0;
	while(added < n - 1)
	{
		int x,y,c;
		std::tie(x,y,c) = pq.top();
		pq.pop();
		if (!ds.AreTheSame(x,y))
		{
			solution.emplace_back(x,y);
			ds.Associate(x, y);
			sum += c;
			++added;
		}
	}
	fm << sum << "\n" << solution.size() << "\n";
	for (const auto edge : solution)
	{
		fm << edge.first << " " << edge.second << "\n";
	}
	return 0;
}