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

//Definitii
#define muchie pair<int, pair<int, int> >
#define cost first
#define from second.first
#define to second.second

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

//Functii
inline int getRadacina(int node);

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

int n, m;
int sum;
int tata[MAX_SIZE];

vector<pair<int, int> > rasp;
vector<pair<int, int> >::iterator it, end;

muchie curent;
priority_queue<muchie, vector<muchie>, greater<muchie> > q;

//Main
int main()
{
	in >> n >> m;
	int cFrom, cTo, cCost;
	for(int i=1 ; i<=m ; ++i)
	{
		in >> cFrom >> cTo >> cCost;
		q.push(make_pair(cCost, make_pair(cFrom, cTo)));
		//q.push(make_pair(cCost, make_pair(cTo, cFrom)));
	}
	
	while(!q.empty())
	{
		curent = q.top();
		q.pop();
		int radacina1 = getRadacina(curent.from);
		int radacina2 = getRadacina(curent.to);
		
		if(radacina1 == radacina2)
			continue;
		
		sum += curent.cost;
		rasp.push_back(make_pair(curent.from, curent.to));
		tata[radacina2] = radacina1;
	}
	
	out << sum << '\n' << rasp.size() << '\n';
	
	end = rasp.end();
	for(it=rasp.begin() ; it!=end ; ++it)
		out << it->first << ' ' << it->second << '\n';
	
	in.close();
	out.close();
	return 0;
}

inline int getRadacina(int node)
{	return (tata[node])? (tata[node] = getRadacina(tata[node])) : (node);	}