#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 , y = x;
    for( R= TT[x] ; R!= TT[R] ; R= TT[R] );
    for ( ; x != R ; y = TT[x] , TT[x] = R , x= y );
    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;


}