#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::vector<Triple>			Tree;

Edges				edges;
int					used[MAX_N];
int					nrUsed;
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;

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

	int costAll = 0;
	used[1] = 1;
	nrUsed ++;

	while(nrUsed != N)
	{
		/*while(used[edges.begin()->dest])
			edges.erase(edges.begin());*/

		Triple triple;

		{
			Edges::const_iterator		itTriple;

			for (itTriple = edges.begin(); edges.end() != itTriple; ++ itTriple)
			{
				if (used[itTriple->source] && !used[itTriple->dest])
				{
					triple = *itTriple;
					edges.erase(itTriple);
					break;
				}
				else if (!used[itTriple->source] && used[itTriple->dest])
				{
					triple = Triple(itTriple->dest, itTriple->source, itTriple->cost);
					edges.erase(itTriple);
					break;
				}
			}
		}
				
		costAll += triple.cost;

		solution.push_back(Triple(triple.source, triple.dest, triple.cost));
		
		used[triple.dest] = 1;
		nrUsed ++;
	}

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

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

	return 0;
}