#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::unordered_map<int, std::list<int>> forrest;
	std::vector<int> indices;
	const int N;
	DS(int N) : N(N)
	{
		indices.reserve(N+1);
		int x = 0;
		std::generate_n(indices.begin(), N + 1, [&x]() { return x++;});
		x = 1;
		for (x = 1; x <= N; ++x)
		{
			std::list<int> s{x};
			forrest[x] = s;
		}
	}
	void Associate(int x, int y)
	{
		const auto id1 = indices[x];
		const auto id2 = indices[y];
		if (id1 == id2)
			return;

		auto& s1 = forrest[id1];
		auto& s2 = forrest[id2];
		
		for (const auto i : s2){
			indices[i] = id1;
		}
		s1.splice(s1.end(), s2);
	}
	bool AreTheSame(int x, int y) const
	{
		return indices[x] == indices[y];
	}
	bool Full() const
	{
		return forrest.at(indices[1]).size() == N;
	}
};
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;
	while (m--)
	{
		fm >> x >> y >> c;
		pq.emplace(x,y,c);
	}
	while(!ds.Full())
	{
		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;
		}
	}
	fm << sum << "\n" << solution.size() << "\n";
	for (const auto edge : solution)
	{
		fm << edge.first << " " << edge.second << "\n";
	}
	return 0;
}