#include <algorithm>
#include <bitset>
using namespace std;

#define DIM 1<<18

struct muchie {

    int c, x, y;
};

int N, M;
int cnt, cst_min, r[ DIM ], t[ DIM ];
bitset <DIM<<1> f;
muchie m[ DIM<<1 ];

struct cmp {

    bool operator()( const muchie &a, const muchie &b ) {

        return a.c < b.c;
    }
};

inline int find( const int &x ) {

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

    return t[ x ];
}

inline void unite( const int &x, const int &y ) {

    if( r[ x ] < r[ y ] )
        t[ x ] = y;
    else
        t[ y ] = x;

    if( r[ x ] == r[ y ] )
        ++r[ x ];
}

int main() {

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

    int i, nod_x, nod_y;

    scanf( "%d %d", &N, &M );
    for( i = 1; i <= M; ++i )
        scanf( "%d %d %d", &m[ i ].x, &m[ i ].y, &m[ i ].c );

    sort( m+1, m+M+1, cmp() );

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

    for( i = 1; i <= M; ++i ) {

        nod_x = find( m[ i ].x );
        nod_y = find( m[ i ].y );
        if( find( nod_x ) != find( nod_y ) ) {

            unite( nod_x, nod_y );
            ++cnt;
            f[ i ] = true;
            cst_min += m[ i ].c;
        }
    }

    printf( "%d\n%d\n", cst_min, cnt );
    for( i = 1; i <= M; ++i )
        if( f[ i ] == true )
            printf( "%d %d\n", m[ i ].x, m[ i ].y );

    return 0;
}