#include<cstdio>
#include<algorithm>

using namespace std ;

#define NMAX 100


int n , m ,a[NMAX],b[NMAX],c[NMAX],ind[NMAX],r[NMAX],mc[NMAX],h[NMAX];
int  nrnd = 0  ,cost=0  ;

int sortrule( int  i  ,int  j )
{
	return c[i]  <  c[j] ? 1 : 0;
}

void uneste ( int a , int b )
{
	if ( h[ a ] > h[ b ] ) 
	{
		r [ b ] = a;
		
		
	}
	else
	{
		r[ a ] = b;		
		
	}
	if ( h [a ] == h[ b ]) ++h [ b ];
}
int  verifica ( int x )
{
	
	int temp = x,rad;
	
	while ( r [ temp ]!=-1 )  temp =r [ temp ] ;
		
	rad = temp; 
		
	while ( r [ x ] != -1 ) 
	{
		temp = x ;
		x = r [ x ];
		r [ temp ] = rad ;		
	}

	return rad ;
}

int main()
{
	freopen( "apm.in" , "r" , stdin );
	freopen( "apm.out" , "w",stdout );

	scanf("%d%d",&n,&m);

	for(int i = 1  ; i <= m  ;  ++i)
	{
		scanf("%d%d%d",&a[i], &b[i], &c[i]);
		ind[i]=i;
	}

	



	sort(ind+1,ind+m+1,sortrule);

	

	for( int i=1 ; i<=n; ++i)
	{
		r[i]=-1;
	}
	

	int x ; int y ;
	int r1,r2;

	for( int i=1 ;  i <= m && nrnd < n-1 ; ++i )
	{
		x=  a[ ind [ i] ] ;
		y= b[ind [ i ] ] ;
		r1= verifica(x) ;
		r2= verifica(y);
		if(r1 != r2 )
		{
			
			++nrnd;
			cost += c[ ind[i] ] ;
			mc[nrnd]=ind[i];
			uneste(x,y);
		
		}
	}


		printf("%d\n%d\n",cost,nrnd);
		for ( int i=1 ; i <= nrnd ; ++i )
		{
			printf("%d %d\n" , a[ mc[i] ] ,b[ mc[i ] ]  ) ;

		}


	return 0;
}