#include <fstream>
 #include <vector>
 #include <algorithm>


 #define MAX_SIZE 400005

 using namespace std;

 ifstream in ( "apm.in" );
 ofstream out ( "apm.out" );

 struct Edge {
	int x , y , c;
	  inline bool operator() ( const Edge &a , const Edge &b ){
	  return a.c < b. c ;
      }
 };
 
 int TT[MAX_SIZE];
 Edge E[MAX_SIZE];
 int N , M, Answer ;
 vector < pair < int , int > > Solution ;
 
 inline int Find ( int x )
 {
	 int R ;
	 for( R= TT[x] ; R!= TT[R] ; R= TT[R] );
	 return R;
	 
 }
 
 int main ( void )
 {
	 int i , j ;
	 in >> N >> M ;
	 for ( i = 1 ; i <= M ; ++i )
     	 in >> E[i].x >> E[i].y >> E[i].c ;
     for ( i = 1 ; i <= N ; TT[i] = i , ++i ) ;
	 sort ( E +1 , E+ M + 1 , Edge() ) ;
	 for ( i = 1 ; i <= M ; ++i )
	 {
		int x = Find( E[i].x ) , y = Find( E[i].y) ;
		if ( x != y )
		{
			Answer += E[i].c;
			TT[x] = y ;
			Solution.push_back( make_pair( E[i].x  , E[i].y) ) ;
		}
					
	 }
	 out << Answer << "\n"<< Solution.size() << "\n";
	 for ( vector < pair < int , int > > ::iterator it = Solution.begin() ; it != Solution.end() ; ++it )
		 out << it->first << " " << it->second << "\n";
	 in.close();
	 out.close();
	 return 0;
	 
	 
 }