// http://infoarena.ro/problema/apm
// http://en.wikipedia.org/wiki/Kruskal's_algorithm
#include <fstream>
#include <algorithm>
using namespace std;

#define maxNodes 200001
#define maxEdges 400001

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

struct stuff {
	int from,to,cost;
};

int nodes,nrEdges,totalCost;
int Link[maxEdges];
int group[maxNodes];
int tree[maxNodes];
stuff edge[maxEdges];

bool comp(int first,int second);
int findAndUpdate(int node);

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

	for(int i=1;i<=nrEdges;i++) {
		in >> edge[i].from >> edge[i].to >> edge[i].cost;
		Link[i] = i;
	}

	// se sorteaza indicii muchiilor (dupa costul acestora)
	sort(Link+1,Link+nrEdges+1,comp);

	// initial fiecare nod este un arbore
	for(int i=1;i<=nodes;i++)
		group[i] = i;

	int usedEdges = 0;
	// se iau toate muchiile in ordine crescatoare dupa costul lor
	for(int i=1;i<=nrEdges;i++)
		// daca muchia uneste doua noduri din componente conexe diferite (arbori diferiti)
		if(findAndUpdate(edge[Link[i]].from) != findAndUpdate(edge[Link[i]].to)) {
			totalCost += edge[Link[i]].cost;	// creste costul arborelui
			
			// se unesc cei doi arbori
			group[ findAndUpdate(edge[Link[i]].from) ] = findAndUpdate(edge[Link[i]].to);

			tree[++usedEdges] = Link[i];	// se retine indicele muchiei pentru afisare
		}

	out << totalCost << "\n";
	out << usedEdges << "\n";
	for(int i=1;i<=usedEdges;i++)
		out << edge[tree[i]].from << " " << edge[tree[i]].to << "\n";

	in.close();
	out.close();

	return (0);
}

bool comp(int first,int second) {
	return (edge[first].cost < edge[second].cost);
}

int findAndUpdate(int node) {
	// daca s-a ajuns la radacina arborelui
	// (nodul pointeaza catre el insusi)
	if(group[node] == node)
		return node;
	else {
		// aplic compresia drumurilor
		// (actualizeaz cu radacina arborelui)
		group[node] = findAndUpdate(group[node]);
		return group[node];
	}
}