#include <cstdio>
#include <queue>
using namespace std;

#define NMAX 200005

int P[ NMAX ], T[ NMAX ];
vector < pair < int, int > > Sol;
priority_queue < pair < int, pair < int, int > > > Q;

int Root( int x ) {

    if ( P[ x ] == P[ P[ x ] ] ) {
        return P[ x ];
    }

    return P[ x ] = Root( P[ x ] );

}

int main () {

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

    int n, m, i, j, a, b, c, cost;
    cost = 0;

    scanf( "%d%d", &n,&m );
    while ( m-- ) {
        scanf ( "%d%d%d", &a,&b,&c );
        Q.push( { -c, { a, b } } );
    }

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

    while ( !Q.empty() ) {
        a = Q.top().second.first;
        b = Q.top().second.second;
        if ( Root( a ) != Root( b ) ) {
            P[ P[ a ] ] = Root( b );
            cost -= Q.top().first;
            Sol.push_back( { a, b } );
        }
        Q.pop();
    }

    printf( "%d\n%d\n", cost, n - 1 );
    for ( i = 0; i < n - 1; ++i )
        printf( "%d %d\n", Sol[ i ].first, Sol[ i ].second );

    return 0;

}