#include <fstream>
#include <algorithm>

#define rint register int

const char IN [ ] = "apm.in" ;
const char OUT [ ] = "apm.out" ;
const int MAX = 400014 ;

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

struct arb {
    int x , y , cost ;
};
arb q [ MAX ] ;
arb sol [ MAX >> 1 ];
int tata [ MAX >> 1 ] , rang [ MAX >> 1 ] ;
int stramos ( int x )
{
    int R ;
    for ( R = x ; tata [ R ] != R ; R = tata [ R ] );
    while ( tata [ x ] != x )
    {
        int aux = tata [ x ] ;
        tata [ x ] = R ;
        x = aux ;
    }
    return R;
}
void unite ( int x , int y )
{
    if ( rang [ x ] > rang [ y ] )
    {
        rang [ x ] += rang [ y ] ;
        tata [ y ] = x ;
    }
    else {
        rang [ y ] += rang [ x ] ;
        tata [ x ] = y ;
    }
}
bool cmp ( arb a , arb b )
{
    return a.cost < b.cost ;
}
long long cost ;
int p ;
int main( )
{
    int n , m ;
    fin >> n >> m ;
    for ( rint i = 1 ; i <= n ; ++ i )
    {
        rang [ i ] = 1 ;
        tata [ i ] = i ;
    }
    for ( rint i = 1 ; i <= m ; ++ i )
        fin >> q [ i ].x >> q [ i ].y >> q [ i ].cost ;
    sort( q + 1 , q + m + 1 , cmp ) ;
    for ( rint i = 1 ; i <= m ; ++ i )
    {
        if ( stramos ( q [ i ]. x ) != stramos ( q [ i ].y ) )
        {
            cost += q [ i ].cost ;
            ++ p ;
            sol [ p ].x = q [ i ].x ;
            sol [ p ].y = q [ i ].y ;
            unite( stramos( q[ i ].x ) , stramos( q[ i ].y ));
        }
    }
    fout << cost << '\n' ;
    fout << p << '\n' ;
    for ( rint i = 1 ; i <= p ; ++ i )
        fout << sol [ i ].x << ' ' << sol [ i ].y << '\n' ;
    return 0;
}