//algoritmul lui Kruskal
#include <stdio.h>
#define N_MAX 200000
#define M_MAX 400000

int v1[ M_MAX + 1 ], v2[ M_MAX + 1 ], val[ M_MAX + 1 ], point[ M_MAX + 1 ];
char ad[ M_MAX + 1 ];
int tata[ N_MAX + 1 ];

int tsup ( int x ){
    if ( tata[ x ] == 0 ){
        return x;
    }
    tata[ x ] = tsup ( tata[ x ] );
    return tata[ x ];
}

void uneste ( int x, int y ){
    tata[ tsup( x ) ] = tsup( y );
    return ;
}

void qs ( int st, int dr ){
    int i = st, j = dr, aux, piv = val[ point[ ( st + dr ) / 2 ] ];
    while ( i <= j ){
        while ( val[ point[ i ] ] < piv )    i++;
        while ( val[ point[ j ] ] > piv )    j--;
        if ( i <= j ){
            aux = point[ i ];  point[ i ] = point[ j ];  point[ j ] = aux;
            i++;  j--;
        }
    }
    if ( st < j )   qs ( st, j );
    if ( i < dr )   qs ( i, dr );
    return ;
}

int main()
{
    FILE *in = fopen ( "apm.in", "r" );
    int n, m;
    fscanf ( in, "%d%d", &n, &m );
    int i;
    for ( i = 1; i <= m; i++ ){
        fscanf ( in, "%d%d%d", &v1[ i ], &v2[ i ], &val[ i ] );
        point[ i ] = i;
    }
    fclose ( in );
    qs ( 1, m );
    int nr = 1, rez = 0;
    for ( i = 1; i <= m && nr < n; i++ ){
        if ( tsup ( v1[ point[ i ] ] ) != tsup ( v2[ point[ i ] ] ) ){
            uneste ( v1[ point[ i ] ], v2[ point[ i ] ] );
            nr++;
            ad[ point[ i ] ] = 1;
            rez += val[ point[ i ] ];
        }
    }
    FILE *out = fopen ( "apm.out", "w" );
    fprintf ( out, "%d\n%d\n", rez, n - 1 );
    for ( i = 1; i <= m; i++ ){
        if ( ad[ i ] ){
            fprintf ( out, "%d %d\n", v1[ i ], v2[ i ] );
        }
    }
    fclose ( out );
    return 0;
}