#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 200011
#define oo 1<<20

using namespace std;
struct vertex
{
	int x, y;
	int cost;
	vertex() : x(0), y(0), cost(oo) {}
	vertex( int _x, int _y, int _cost ) : x(_x), y(_y), cost(_cost) {}
	inline bool operator<( const vertex& z ) const
	{
		return ( cost == z.cost ? ( x == z.x ? y < z.y : x < z.x ) : cost < z.cost  );
	}
	friend inline istream& operator>>( istream& in, vertex& z )
	{
		in>>z.x>>z.y>>z.cost;
		return in;
	}
	friend inline ostream& operator<<( ostream& out, const vertex& z )
	{
		out<<z.x<<' '<<z.y;
		return out;
	}
};
int f[N_MAX], r[N_MAX];
vector< vertex > apm, v;
vector< vertex >::const_iterator it, iend;
inline int _min( int x, int y ) { return ( x <= y ? x : y ); }
inline 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 unite( int x, int y )
{
	if( r[x] == r[y] )
	{
		if( x != y )
			f[y]=x;
		++r[y];
	}
	else r[x]=r[y]=_min( r[x], r[y] );
}
int main( void )
{
	int N, M, i, s=0;
	ifstream in( "apm.in" );
	in>>N>>M;
	for( i=1; i <= N; ++i )
		f[i]=i, r[i]=1;
	copy( istream_iterator<vertex>(in), istream_iterator<vertex>(), back_inserter(v) );
	sort( v.begin(), v.end() );
	for( i=1, it=v.begin(), iend=v.end(); it < iend && i < N; ++it )
	{
		int fx=find( it->x ), fy=find( it->y ), c=it->cost;
		if( fx != fy )
		{
			apm.push_back( *it );
			s+=c;
			unite( fx, fy );
		}
	}
	ofstream out( "apm.out" );
	out<<s<<'\n'<<(N-1)<<'\n';
	copy( apm.begin(), apm.end(), ostream_iterator<vertex>( out, "\n" ) );
	return EXIT_SUCCESS;
}