# include <fstream>
 # include <algorithm>
 
 # define dim 400005
 
 using namespace std;
 
 ifstream f("apm.in");
 ofstream g("apm.out");
 
 struct arbore
 {
	 int n1, n2, c;
 };
 
 inline int cmp( arbore a, arbore b )
 {
	 return a.c < b.c;
 }
 
 
 arbore a[ dim ];
 int costmin, c[ dim ], n, m, sol[ dim ], cnt;
 
 inline void citire()
 {
	 int i;
	 f >> n >> m;
	 for ( i = 1 ; i <= m ; i++ )
		 f >> a[ i ].n1 >> a[ i ].n2 >> a[ i ].c;
 }
 
 inline void conex()
 {
	 int i;
	 for ( i = 1 ; i <= n ; i++ )
		 c[ i ] = i;
 }
 
 int cauta( int x )
 {
	 int r = x, y;
	 
	 while ( r != c[ r ] )
		 r = c[ r ];
	 
	 while ( x != c[ x ] )
	 {
		 y = r;
		 c[ x ] = y;
		 x = c[ x ];
	 }
	 
	 return r;
 }
 
 inline void leaga( int x, int y )
 {
	 c[ x ] = y;
 }
 
 inline void rezolva()
 {
	 int i, n1, n2;
	 sort( a + 1, a + m + 1, cmp );
	 
	 for ( i = 1 ; i <= m && cnt < n ; i++ )
	 {
		 n1 = cauta( a[ i ].n1 );
		 n2 = cauta( a[ i ].n2 );
		 
		 
		 
		 if ( n1 != n2 )
		 {
			 leaga( n1, n2 );
			 cnt ++;
			 sol[ cnt ] = i;
			 costmin = costmin + a[ i ].c;
		 }
	 }
	 g << costmin << "\n";
	 g << cnt << "\n";
	 for ( i = 1 ; i <= cnt ; i++ )
		 g << a[ sol[ i ] ].n1 << " " << a[ sol[ i ] ].n2 << "\n";
	 
	  //for ( i = 1 ; i <= n ; i++ )
		 // g << c[ i ] << " ";
	 
 }
 
 int main()
 {
	 citire();
	 conex();
	 rezolva();
	 return 0;
 }