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

const int maxn = 200200, inf = 200000200;
int vec[ maxn ], ans, v[ maxn ], h[ maxn * 2 + 100 ], poz[ maxn ];
vector< pair<int,int> > vect[ maxn ], vans;
int n, m, l, c[ maxn ];

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 poz2 )
{
	while ( ( poz2 * 2 <= l && v[ h[ poz2 ] ] > v[ h[ poz2 * 2 ] ] ) || ( poz2 * 2 + 1 <= l && v[ h[ poz2 ] ] > v[ h[ poz2 * 2 + 1 ] ] ) )
	{
		if ( v[ h[ poz2 * 2 ] ] < v[ h[ poz2 * 2 + 1 ] ] || poz2 * 2 + 1 > l )
		{
			swap( h[ poz2 ],h[ poz2 * 2 ] );
			swap( poz[ h[ poz2 ] ],poz[ h[ poz2 * 2 ] ] );
			poz2 *= 2;
		}
		else
		{
			swap( h[ poz2 ],h[ poz2 * 2 + 1 ] );
			swap( poz[ h[ poz2 ] ],poz[ h[ poz2 * 2 + 1 ] ] );
			poz2 = poz2 * 2 + 1;
		}
	}
}

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

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

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

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;
}