/**
*	Arbore Partial de cost Minim
* 	Implementare pe STL
*/
#include <fstream>
#include <vector>
#include <algorithm>

#define NMAXVF 200001

using namespace std;

struct Muchii {
	unsigned int nod1;
	unsigned int nod2;
	short int cost;
} tmp;

/* lista de muchii */
vector<Muchii> Graf;

/* A - APM - indicii muchiilor alese */
int A[NMAXVF], C[NMAXVF];	// C[i] = nr componentei conexe din care face parte nodul i

/* N = nr noduri, M = nr muchii */
int N, M, costAPM;

void citire();
void afisare();
void kruskal();

bool sortareMuchii(Muchii a, Muchii b) {
	return a.cost < b.cost;
}

int main() {
	citire();
	kruskal();
	afisare();
}

void kruskal() {
	/* sortez muchiile crescator dupa cost */
	sort(Graf.begin() + 1, Graf.begin() + 1 + M, sortareMuchii);	
	// lucrez pe STL dar nu cu iteratori
	
	int NrMSel = 0;		// numarul de muchii selectate
	int min, max;		
	
	for(int i=1; NrMSel < N-1; ++i) {
		// daca muchia i nu formeaza cicluri cu cele deja existente
		if(C[Graf[i].nod1] != C[Graf[i].nod2]) {
			// selectez muchia i
			A[++NrMSel] = i;
			// costul total APM
			costAPM += Graf[i].cost;
	
			// cele doua noduri gasit vor face parte din aceasi compoeneta conexa
			// fac cu min/max pt ca vreau ca indici minimi la comp conexe
			if(C[Graf[i].nod1] < C[Graf[i].nod2]) {
				min = C[Graf[i].nod1];
				max = C[Graf[i].nod2];
			}
			else {
				min = C[Graf[i].nod2];
				max = C[Graf[i].nod1];
			}
			// update
			for(int j=1; j<=N; j++)
				if(C[j] == max)
					C[j] = min;	
		}
	}
	
	//for(int i=1; i<=M; i++) {
	//	cout << Graf[i].nod1 <<' '<< Graf[i].nod2 <<' '<< Graf[i].cost<<'\n';
	//}
}

void afisare() {
	ofstream fout("apm.out");
	fout << costAPM << '\n' << N-1 << '\n';
	for(int i=1; i<N; ++i) {
		fout<<Graf[A[i]].nod1<<' '<<Graf[A[i]].nod2<<'\n';
	}
	fout.close();
}

void citire() {
	ifstream fin("apm.in");
	fin >> N >> M;
	
	// aloc zona de memorie pt muchii
	Graf.reserve(M+1);
	for(int i=1; i<=M; i++) {
		fin >> Graf[i].nod1 >> Graf[i].nod2 >> Graf[i].cost;
		//fin >> tmp.nod1 >> tmp.nod2 >> tmp.cost;
		//Graf.push_back(tmp);
	}
	
	// initial - fiecare nod e izolat
	for(int i=1; i<=N; i++) 
		C[i] = i;
	fin.close();
}