// cu multimi disjuncte vad daca noua latura va creea un ciclu ( va fi in una din componentele conexe create in APM-ul in formare )
// O( MlgN + MlgM )

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define cost first 
#define x second.first
#define y second.second

const int Mmax=400011;
const int Nmax=200011;

pair< int , pair< int,int > > A[Mmax];
int N,M,Ans,Gr[Nmax];
vector< pair<int,int> > V;

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

int Grup(int i)
{
	if (Gr[i] == i) return i;
	Gr[i] = Grup(Gr[i]);
	return Gr[i];
}

void Union(int i,int j)
{	Gr[ Grup(i) ] = Grup(j) ; }


int main()
{
	F>>N>>M;
	
	for (int i=1;i<=N;++i) Gr[i]=i;
	for (int i=1;i<=M;++i) F>>A[i].x>>A[i].y>>A[i].cost;
	
	sort(A+1,A+M+1);
	
	for (int i=1;i<=M;++i)
		if ( Gr[Grup(A[i].x)] != Gr[Grup(A[i].y)] )
		{
			Ans+=A[i].cost;
			V.push_back( make_pair( A[i].x , A[i].y ) );
			Union( A[i].x , A[i].y );
		}
		
	G<<Ans<<'\n';
	G<<V.size()<<'\n';
	while ( V.size() )
	{
		G<<V.back().first<<' '<<V.back().second<<'\n';
		V.pop_back();
	}
}