#include <bits/stdc++.h>

struct gogu {
    int x, y, cost;
} mk[400000];

int compar( gogu A, gogu B ) {
    return A.cost < B.cost;
}

std::vector< std::pair< int, int > >arb;
int dad[200001];

int boss( int sclav ) {
    if ( dad[sclav] != sclav )
        dad[sclav] = boss( dad[sclav] );
    return dad[sclav];
}

int main()  {
    FILE *fin, *fout;
    int n, m, i, s = 0;
    fin = fopen( "apm.in", "r" );
    fout = fopen( "apm.out", "w" );
    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ )
        fscanf( fin, "%d%d%d", &mk[i].x, &mk[i].y, &mk[i].cost );
    std::sort( mk, mk + m, compar );
    for ( i = 1; i <= n; i++ )
        dad[i] = i;
    i = 0;
    while ( arb.size() < n - 1 ) {
        if ( boss( mk[i].x ) != boss( mk[i].y ) ) {
            dad[boss( mk[i].x )] = boss( mk[i].y );
            s += mk[i].cost;
            arb.push_back( { mk[i].x, mk[i].y } );
        }
        i++;
    }
    fprintf( fout, "%d\n%d\n", s, arb.size() );
    for ( i = 0; i < arb.size(); i++ )
        fprintf( fout, "%d %d\n", arb[i].first, arb[i].second );
    fclose( fin );
    fclose( fout );
    return 0;
}