/*arbore partial de cost min
ordonarea dupa cost a arcelor
reuniunea lor in multimi folosind
euristicii reuniune dupa rang si
compresia drumurilor
*/

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

using namespace std;


const int MAX = 400010;

int IND [ MAX ] , CLS [ 200010 ];

struct arc{
    int x , y , c ;

} MUCHIE [ MAX ];


bool myCmp( arc i ,arc j){

    return (  i.c < j.c ) ;
}

int findParent ( int x ) {

    /*
    if ( x == CLS [ x ] )   return x;
    CLS [ x ] = findParent( CLS [ x ] );
    */
    vector <int> actualizari ;
    while ( x != CLS [ x ] ){
        actualizari.push_back( x );
        x = CLS [ x ];
    }
    for ( int  i = 0 ; i < actualizari.size() ; i++ )
        CLS [ actualizari [ i ] ] = x;

    return x;


}

void Union (int x, int y){

    x = findParent ( x );
    y = findParent ( y );
    CLS [ x ] = y;

}

int main()
{
    int n,m,x,y,c,i = 0 ,cpy_m , ANS = 0 ;
    vector < int > MCH ;

    ifstream f( "apm.in" , ios::in);
    ofstream g ( "apm.out" , ios::out);

    f>>n>>m;
    cpy_m = m;

    for ( i = 1 ; i <= n ; i++)
        CLS [ i ] = i;

     i = 0 ;

    while ( cpy_m-- && ++i ){

        f>>x>>y>>c;
        MUCHIE [ i ].x = x;
        MUCHIE [ i ].y = y;
        MUCHIE [ i ].c = c;

    }

    sort (MUCHIE + 1, MUCHIE + m + 1, myCmp );

    for ( i = 1 ; i <= m ; i++){
        if ( findParent( MUCHIE [ i ].x ) != findParent( MUCHIE [ i ].y )  ){

            Union (  MUCHIE [ i ].x ,  MUCHIE [ i ].y  ) ;
            ANS+= MUCHIE [ i ].c;
            MCH.push_back( i );

        }

    }

    g<<ANS<<"\n"<<MCH.size()<<"\n";

    for ( i = 0 ; i < MCH.size() ; i++)
        g<<MUCHIE [ MCH [ i ] ].x <<" "<< MUCHIE [ MCH [ i ] ].y<<"\n";


    return 0;
}