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

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

int n,m;
muchie M[400000];
int C[200000]; //Codificarea Componentei conexe Din care face paret fiecare nod.
			   //Initial C[i]=i, pentru i=1..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;
}

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;

	for(int i=1;i<=n;i++){ C[i]=i; }
	int ct=0, x, y, cost=0;
	for(int i=1;i<=m;i++){
		x=M[i].x; y=M[i].y;
		if(C[x]!=C[y]){
			K[++ct]=M[i];
			cost+=M[i].cost;
			replace(C+1,C+n+2,C[x],C[y]);
		}
		if(ct==n-1){
			break;
		}
	}

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