#include <algorithm>
#include <vector>

using namespace std;

#define MAX_N 200005
#define MAX_S 10005

char s[ MAX_S ];
int N, M;
int cnt_s, cst_min, r[ MAX_N ], t[ MAX_N ];
vector < pair <int, int> > sol;
vector < pair < int, pair <int, int> > > m;

int find( const int &nod ) {

    if( nod != t[ nod ] )
        t[ nod ] = find( t[ nod ] );

    return t[ nod ];
}

void unite( const int &nod_1, const int &nod_2 ) {

    if( r[ nod_1 ] < r[ nod_2 ] )
        t[ nod_1 ] = nod_2;
    else
        t[ nod_2 ] = nod_1;

    if( r[ nod_1 ] == r[ nod_2 ] )
        ++r[ nod_1 ];
}

void read( int &val ) {

    int sgn;

    sgn = 1;
    while( !isdigit( s[ cnt_s ] ) ) {

        if( s[ cnt_s ] == '-' )
            sgn = -1;
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }
    }

    val = 0;
    while( isdigit( s[ cnt_s ] ) ) {

        val = val * 10 + s[ cnt_s ] - '0';
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }
    }

    val *= sgn;
}

int main() {

    freopen( "apm.in", "r", stdin );
    freopen( "apm.out", "w", stdout );

    int i, c, x, y, t_1, t_2;
    vector < pair <int, int> > :: iterator it_1;
    vector < pair < int, pair <int, int> > > :: iterator it_2;

    cnt_s = MAX_S - 1;

    read( N );
    read( M );

    while( M-- ) {

        read( x );
        read( y );
        read( c );

        m.push_back( make_pair( c, make_pair( x, y ) ) );
    }

    sort( m.begin(), m.end() );

    for( i = 1; i <= N; ++i )
        t[ i ] = i;

    for( it_2 = m.begin(); it_2 != m.end(); ++it_2 ) {

        t_1 = find( it_2->second.first );
        t_2 = find( it_2->second.second );

        if( t_1 != t_2 ) {

            unite( t_1, t_2 );

            cst_min += it_2->first;
            sol.push_back( make_pair( it_2->second.first, it_2->second.second ) );
        }
    }

    printf( "%d\n%d\n", cst_min, sol.size() );
    for( it_1 = sol.begin(); it_1 != sol.end(); ++it_1 )
        printf( "%d %d\n", it_1->first, it_1->second );

    return 0;
}