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