#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 200011
#define pr pair< int, int >
#define prr pair< int, pr >

using namespace std;
int N;
int f[N_MAX], r[N_MAX];
vector< prr > v;
vector< pr > apm;
vector< prr >::const_iterator it, iend;
int Find( int x )
{
	int y, z;
	for( y=f[x]; y != f[y]; y=f[y] );
	for( ; x != f[x]; x=z )
	{
		z=f[x];
		f[x]=y;
	}
	return y;
}
inline void Union( int x, int y )
{
	if( r[x] == r[y] )
	{
		if( x != y )
			f[x]=y;
		++r[x];
	}
	else r[x]=r[y]= r[x] <= r[y] ? r[x] : r[y];
}
int main( void )
{
	int s=0;
	int M, x, y, c, i, Fx, Fy;
	ifstream in( "apm.in" );
	for( in>>N>>M; M; --M )
	{
		in>>x>>y>>c;
		v.push_back( prr( c, pr( x, y ) ) );
	}
	for( i=1; i <= N; ++i )
		f[i]=i, r[i]=1;
	sort( v.begin(), v.end() );
	ofstream out( "apm.out" );
	for( i=0, it=v.begin(), iend=v.end(); it < iend; ++it )
	{
		x=it->second.first;	y=it->second.second;
		Fx=Find(x);	Fy=Find(y);
		if( Fx != Fy )
		{
			s+=it->first;
			apm.push_back( pr( x, y ) );
			Union( Fx, Fy );
			++i;
			if( N == i )
				break;
		}
	}
	out<<s<<'\n'<<(N-1)<<'\n';
	for( i=1; i < N; ++i )
		out<<apm[i-1].first<<' '<<apm[i-1].second<<'\n';
	return EXIT_SUCCESS;
}