// http://infoarena.ro/problema/apm
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define from first
#define cost first
#define to second

const int MAXSIZE = 200001;

ifstream in("apm.in");
ofstream out("apm.out");

int nodes,nrEdges,treeCost;
int father[MAXSIZE];
vector< pair<int,int> > selectedEdges;
priority_queue< pair<int,pair<int,int> >,
	vector< pair<int,pair<int,int> > >,
	greater< pair<int,pair<int,int> > > > edges;

void join(int first,int second);
int getFather(int node);

int main()
{
	in >> nodes >> nrEdges;

	pair< int,pair<int,int> > currentEdge;
	for(int i=1;i<=nrEdges;i++)
	{
		in >> currentEdge.second.from;
		in >> currentEdge.second.to;
		in >> currentEdge.cost;

		edges.push(currentEdge);
	}
	in.close();

	while(!edges.empty() && selectedEdges.size() != nodes)
	{
		currentEdge = edges.top();
		edges.pop();

		if(getFather(currentEdge.second.from) != getFather(currentEdge.second.to))
		{
			join(getFather(currentEdge.second.from),getFather(currentEdge.second.to));
			selectedEdges.push_back(currentEdge.second);
			treeCost += currentEdge.cost;
		}
	}

	out << treeCost << "\n";
	out << selectedEdges.size() << "\n";

	vector< pair<int,int> >::iterator end = selectedEdges.end();
	for(vector< pair<int,int> >::iterator it=selectedEdges.begin();it!=end;++it)
		out << it->from << " " << it->to << "\n";
	out << "\n";

	out.close();

	return (0);
}

void join(int first,int second)
{
	father[first] = second;
}

int getFather(int node)
{
	if(!father[node])
		return node;
	else
	{
		father[node] = getFather(father[node]);
		return father[node];
	}
}