#include <algorithm>
using namespace std;

#define MAXN 200001
#define MAXM 400001

struct muchie {

    int c, x, y;
};

int n, m, cnt, cost, rg[ MAXN ], tt[ MAXN ], sol[ MAXM ];
muchie a[ MAXM ];

int cmp( muchie a, muchie b ) {

    return a.c < b.c;
}

void init() {

    int i;

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

        rg[ i ] = 1;
        tt[ i ] = i;
    }
}

int find( int x ) {

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

    return tt[ x ];
}

void unite( int x, int y ) {

    if( rg[ x ] < rg[ y ] )
        tt[ x ] = y;
    else
        tt[ y ] = x;
    if( rg[ x ] == rg[ y ] )
        ++ rg[ x ];
}

void read() {

    int i;

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

void solve() {

    int i, x0, y0;

    sort( a + 1, a + m + 1, cmp );
    init();
    for( i = 1; i <= m; ++ i ) {

        x0 = find( a[ i ].x );
        y0 = find( a[ i ].y );
        if( x0 != y0 ) {

            sol[ ++ cnt ] = i;
            cost += a[ i ].c;
            unite( x0, y0 );
        }
    }
    printf( "%d\n%d\n", cost, cnt );
    for( i = 1; i <= cnt; ++ i )
        printf( "%d %d\n", a[ sol[ i ] ].x, a[ sol[ i ] ].y );
}

int main() {

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

    read();
    solve();

    return 0;
}