#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/*************** Disjoint Data Set code ******************/

struct DisjointSet
{
	int parent;
	int rank;
};

void MakeSet(vector<DisjointSet>& dset)
{
	for (int i=0; i<(int)dset.size(); ++i)
	{
		dset[i].parent=i;
		dset[i].rank=0;
	}
}

int Find(vector<DisjointSet>& dset,int x)
{
	if (dset[x].parent==x)
		return x;
	dset[x].parent=Find(dset,dset[x].parent);
	
	return dset[x].parent;
}

void Union(vector<DisjointSet>& dset, int x, int y)
{
	int xRoot=Find(dset,x);
	int yRoot=Find(dset,y);
	
	if (dset[xRoot].rank > dset[yRoot].rank)
		dset[yRoot].parent=xRoot;
	else if (dset[xRoot].rank < dset[yRoot].rank)
		dset[xRoot].parent=yRoot;
	else if (xRoot!=yRoot)
	{
		dset[yRoot].parent=xRoot;
		dset[xRoot].rank++;
	}
}

/*************** Kruskal code ******************/

struct Edge
{
	Edge() {}
	Edge(const int s,
		const int d,
		const short c) : src(s), dest(d), cost(c)
	{
		src = s;
		dest = d;
		cost = c;
	}
	int src, dest;
	short cost;
};

class Comp
{
public:
	inline bool operator ()(const Edge& e1, const Edge& e2) const
	{
		return e1.cost < e2.cost;
	}
};

int Kruskal(const vector<Edge>& edges, vector<Edge>& mst)
{
	int totalCost=0;
	vector<DisjointSet> dset;
	dset.resize(edges.size()+1);
	
	MakeSet(dset);
	
	for (int i=0; i<edges.size(); ++i)
	{
		if (Find(dset,edges[i].src) != Find(dset,edges[i].dest))
		{
			totalCost += edges[i].cost;
			mst.push_back(edges[i]);
			Union(dset,edges[i].src,edges[i].dest);
		}
	}
	
	return totalCost;
}

int main()
{
	int n, m, totalCost;
	Comp comp;
	vector<Edge> edges, output;
	fstream fin("apm.in", fstream::in);
	fstream fout("apm.out", fstream::out);
	
	fin >> n >> m;
	//cout << n << " " << m << endl;
	
	for (int i=0; i<m; ++i)
	{
		int src, dest;
		short cost;
		fin >> src >> dest >> cost;
		//cout << src << " " << dest << " " << cost << endl;

		edges.push_back(Edge(src, dest, cost));
	}
	
	sort(edges.begin(), edges.end(), comp);
	
	/*cout << endl;
	for (int i=0; i<m; ++i)
	{
		cout << edges[i].src << " " << edges[i].dest << " " << edges[i].cost << endl;
	}*/
	
	totalCost = Kruskal(edges, output);
	
	fout << totalCost << "\n";
	fout << output.size() << "\n";
	
	for (int i=0; i<output.size(); ++i)
	{
		fout << output[i].src << " " << output[i].dest << "\n";
	}
	
	fin.close();
	fout.close();
	return 0;
}