//Arborele Partial de Cost Minim (Minimum spanning tree).
//Algoritmul Kruskal.
//Implementare in m*log(n) utilizind reprezentarea multimilor disjuncte.
#include <fstream>
#include <algorithm>
using namespace std;

struct muchie{
	int x,y,cost;
};

int n,m;
muchie M[400000];
int R[200000]; //Tatal fiecarui Element. Initial R[i]=0, i=1..n;
int H[200000]; //Adincimea fiecarui arbore partia. Initial H[i]=0, i=0..n;
muchie K[200000]; //Vectorul in care tinem Componentele Arborelui Partial

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

bool cmp(muchie A, muchie B)
{
	return A.cost<B.cost;
}

int GetRoot(int x)
{
	while(R[x]){ x=R[x]; }
	return x;
}

void Read()  
{
	//Citim Graful
	//n - Numarul de noduri, variabila globala;
	//m - Numarul de Arce Neorinetate, variabila globala;
	//M - Lista Muchiilor
	inFile >> n >> m;
	for(int i=1; i<=m; i++){
		inFile >> M[i].x >> M[i].y >> M[i].cost;
	}
}

int main()
{
	Read();
	sort(M+1,M+m+1,cmp);  //Sortam Lista de Muchii;

	int ct=0, x, y, cost=0;
	int rx,ry;
	for(int i=1;i<=m;i++){
		x=M[i].x; y=M[i].y;
		rx=GetRoot(x); ry=GetRoot(y);
		if(rx!=ry){
			K[++ct]=M[i];
			cost+=M[i].cost;
			if(rx>ry){ R[ry]=rx; }
			if(rx<ry){ R[rx]=ry; }
			if(rx==ry){ R[rx]=ry; H[ry]++; }
		}
		if(ct==n-1){
			break;  //Arborele Partaial nu are decit n-1 noduri din cele n totale
		}
	}

	outFile << cost << "\n" << n-1 << "\n";
	for(int i=1;i<=ct;i++){
		outFile << K[i].x << " " << K[i].y << "\n";
	}
	
}