#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin( "apm.in" );
ofstream cout( "apm.out" );

int vec[ 200200 ], ans, v[ 200200 ], h[ 400500 ];
int poz[ 200200 ], inf = 200000200;
int n, m, k, c[ 200200 ];
vector< pair<int,int> > vect[ 200200 ], vans;

void introduce_in_apm( int x )
{
	int i, nod, cost;
	for ( i = 0; i < vect[ x ].size(); i++ )
	{
		nod = vect[ x ][ i ].first;
		cost = vect[ x ][ i ].second;
		v[ nod ] = min( v[ nod ],cost );
		if ( v[ nod ] == cost ) vec[ nod ] = x;
	}
}

void push( int nod )
{
	while ( ( nod * 2 <= k && v[ h[ nod ] ] > v[ h[ nod * 2 ] ] ) || ( nod * 2 + 1 <= k && v[ h[ nod ] ] > v[ h[ nod * 2 + 1 ] ] ) )
	{
		if ( v[ h[ nod * 2 ] ] < v[ h[ nod * 2 + 1 ] ] || nod * 2 + 1 > k )
		{
			swap( h[ nod ],h[ nod * 2 ] );
			swap( poz[ h[ nod ] ],poz[ h[ nod * 2 ] ] );
			nod *= 2;
		}
		else
		{
			swap( h[ nod ],h[ nod * 2 + 1 ] );
			swap( poz[ h[ nod ] ],poz[ h[ nod * 2 + 1 ] ] );
			nod = nod * 2 + 1;
		}
	}
}

void pop( int nod )
{
	while ( nod > 1 && v[ h[ nod ] ] < v[ h[ nod / 2 ] ] )
	{
		swap( h[ nod ],h[ nod / 2 ] );
		swap( poz[ h[ nod ] ],poz[ h[ nod / 2 ] ] );
		nod /= 2;
	}
}

void introduce_in_heap( int nod )
{
	h[ ++k ] = nod;
	poz[ nod ] = k;
	pop( k );
}

int scoate_radacina_heap()
{
	int nod;
	nod = h[ 1 ];
	swap( h[ 1 ],h[ k ] );
	swap( poz[ h[ 1 ] ],poz[ h[ k ] ] );
	k--;
	push( 1 );
	poz[ nod ] = 0;
	return nod;
}

int main()
{
	int i, j, x, y, cost, nod;
	cin >> n >> m;
	for ( i = 1; i <= m; i++ )
	{
		cin >> x >> y >> cost;
		vect[ x ].push_back( make_pair( y,cost ) );
		vect[ y ].push_back( make_pair( x,cost ) );
	}
	for ( i = 1; i <= n; i++ )
		v[ i ] = inf;
	v[ 1 ] = 0;
	introduce_in_apm( 1 );
	for ( i = 2; i <= n; i++ )
		introduce_in_heap( i );
	for ( i = 1; i < n; i++ )
	{
		x = scoate_radacina_heap();
		introduce_in_apm( x );
		ans += v[ x ];
		vans.push_back( make_pair( x,vec[ x ] ) );
		for ( j = 0; j < vect[ x ].size(); j++ )
		{
			nod = vect[ x ][ j ].first;
			if ( poz[ nod ] ) pop( poz[ nod ] );
		}
	}
	cout << ans << '\n';
	cout << n - 1 << '\n';
	for ( i = 0; i < n - 1; i++ )
		cout << vans[ i ].first << " " << vans[ i ].second << '\n';
	return 0;
}