#include <fstream>
#include <set>
#include <stack>
#include <vector>

#define MAX_N		((int)200000)
#define INFINITE	((int)0xF0000000)

class Pair
{
public:
	int node;
	int cost;

public:
	Pair(int _node, int _cost) :
	  node(_node), cost(_cost)
	  {

	  }

	  bool operator < (const Pair &_other) const
	  {
		  return this->node < _other.node;
	  }
};

class Triple
{
public:
	int source;
	int dest;
	int cost;

public:
	Triple() : 
	  source(-1), dest(-1), cost(INFINITE)
	{

	}

	Triple(int _source, int _dest, int _cost) : 
	  source(_source), dest(_dest), cost(_cost)
	{

	}

	bool operator < (const Triple &_other) const
	{
		return this->cost < _other.cost;
	}
};

typedef std::multiset<Triple>		Edges;
typedef std::set<int>				Nodes;
typedef std::vector<Pair>			Neighbours;
typedef std::vector<Triple>			Tree;

Edges				edges;
Neighbours			Graf[MAX_N];
Nodes				included;
Tree				solution;

int main()
{	
	int N, M, x, y, c;

	std::ifstream fin("apm.in");
	std::ofstream fout("apm.out");

	fin>>N>>M;

	while(M --)
	{
		fin>>x>>y>>c;

		Graf[x].push_back(Pair(y, c));
		Graf[y].push_back(Pair(x, c));

		edges.insert(Triple(x, y, c));
		edges.insert(Triple(y, x, c));
	}

	int costAll = 0;
	included.insert(1);

	while(included.size() != N)
	{
		while(included.find(edges.begin()->dest) != included.end())
			edges.erase(edges.begin());

		Triple triple;

		{
			Edges::const_iterator		itTriple;

			for (itTriple = edges.begin(); edges.end() != itTriple; ++ itTriple)
			{
				if ((included.find(itTriple->source) != included.end())
					&& (included.find(itTriple->dest) == included.end()))
				{
					triple = *itTriple;
					edges.erase(itTriple);
					break;
				}
			}
		}
				
		costAll += triple.cost;

		solution.push_back(Triple(triple.source, triple.dest, triple.cost));
		included.insert(triple.dest);
	}

	fout<<costAll<<'\n'<<solution.size()<<'\n';

	for (int i = 0; i < solution.size(); ++ i)
		fout<<solution[i].source<<" "<<solution[i].dest<<'\n';
	
	fin.close();
	fout.close();

	return 0;
}