#include <bits/stdc++.h>

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

struct nod {
    int x, y, c;
} mk[400000];

int compar( nod A, nod B ) {
    if ( A.c < B.c )
        return 1;
    return 0;
}

int boss( int slave ) {
    while ( dad[slave] != slave )
        slave = dad[slave];
    return slave;
}

int main() {
    FILE *fin, *fout;
    int n, m, i, s, k;
    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].c );
    std::sort( mk, mk + m, compar );
    for ( i = 1; i <= n; i++ )
        dad[i] = i;
    i = 0;
    k = 0;
    s = 0;
    while ( k < n - 1 ) {
        if ( boss( mk[i].x ) != boss( mk[i].y ) ) {
            s += mk[i].c;
            k++;
            dad[ boss( mk[i].y ) ] = boss( mk[i].x );
            apm.push_back( { mk[i].x, mk[i].y } );
        }
        i++;
    }
    fprintf( fout, "%d\n%d\n", s, n - 1 );
    for ( i = 0; i < n - 1; i++ )
        fprintf( fout, "%d %d\n", apm[i].first, apm[i].second );
    fclose( fin );
    fclose( fout );
    return 0;
}