#include <iostream>
#include <fstream>

using namespace std;

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

int n,m,indx=0;

int L[200001];

struct Structura
{
	int x,y,c;
};

Structura U[400000];
int vect[400000];

void Citire(){

	f >> n >> m;

	for (int i = 0; i < m; ++i)
	{
		f >> U[i].x >> U[i].y >> U[i].c;
	}

}

void Ordonare_U(){

	int ok=0;

	Structura aux;

	while(ok==0){

		ok=1;

		for (int i = 0; i < m-1; ++i)
		{
			if( U[i].c > U[i+1].c){
				ok=0;
				aux=U[i];
				U[i]=U[i+1];
				U[i+1]=aux;
			}
		}
	}
}

void Afisare_U(){

	for (int i = 0; i < m; ++i)
	{
		cout << ' ' << U[i].x << ' ' << U[i].y << ' ' <<  U[i].c << '\n';
	}

}


int Kurksal(){

	int ct=0,k=0,aux=0,nr1,nr2;

	for(int i=1;i<=n;i++)
		L[i]=i;

	while(k<n-1){

		if(L[U[aux].x]!=L[U[aux].y]){

			vect[indx]=aux;
			indx++;
			k++;
			ct+= U[aux].c;
			nr1= L[U[aux].x];
			nr2= L[U[aux].y];

			for(int i=1;i<=n;i++)
				if(L[i]==nr2)
					L[i]=nr1;

		}
		aux++;
	}


	return ct;


}



int main(){

	Citire();
	Ordonare_U();
	//Afisare_U();
	cout << Kurksal() << '\n' << indx << '\n';
	for(int i=0;i<indx;i++)
		cout << U[vect[i]].x << ' ' << U[vect[i]].y << "\n";

	return 0;

}