//Include
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

//Definitii
#define edge pair<int, pair<int, int> >
#define cost first
#define from second.first
#define to second.second
#define pb push_back
#define mp make_pair
#define vIT vector<pair<int, int> >::iterator

//Constante
const int MAX_SIZE = (int)2e5+1;

//Functii
inline int getRoot(int node);

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

int nodes, edges;
int father[MAX_SIZE];
int totalCost;

vector<pair<int, int > > answer;
priority_queue<edge, vector<edge>, greater<edge> > heap;

//Main
int main()
{
	in >> nodes >> edges;
	
	int cFrom, cTo, cCost;
	while(edges--)
	{
		in >> cFrom >> cTo >> cCost;
		heap.push(mp(cCost, mp(cFrom, cTo)));
	}
	
	while(!heap.empty())
	{
		edge top = heap.top();
		heap.pop();
		
		int root1, root2;
		if((root1=getRoot(top.from)) != (root2=getRoot(top.to)))
		{
			father[root2] = root1;
			totalCost += top.cost;
			answer.pb(mp(top.from, top.to));
		}
	}
	
	out << totalCost << '\n' << answer.size() << '\n';
	
	for(vIT it=answer.begin() ; it!=answer.end() ; ++it)
		out << it->first << ' ' << it->second << '\n';
	
	in.close();
	out.close();
	return 0;
}

inline int getRoot(int node)
{	return father[node]? father[node]=getRoot(father[node]) : node;	}