#include<stdio.h>
#include<algorithm>
using namespace std ;
long h [ 200007 ] , r [ 200007 ] , c [ 200007 ] , m , n , xi , yi , nr , num ;
struct brailu
{
    long x , y , cost ;
};
brailu a [ 400007 ] ;
bool cmp ( brailu b , brailu c )
{
    return b . cost < c . cost ;
}
long find ( long i )
{
    if ( i == r [ i ] )
        return i ;
    return find ( r [ i ] ) ;
}
long unite ( long i , long j )
{
    i = find ( i ) ;
    j = find ( j ) ;
    if ( i == j )
        return 0 ;
    if (h [ i ] == h [ j ] )
    {
        ++ h [ i ] ;
        r [ i ] = i ;
    }
    if ( h [ i ] < h [ j ] )
        r [ i ] = j ;
    else
        r [ j ] = i ;
    return 1 ;
}
int main ( )
{
    freopen ( "apm.in" , "r" , stdin ) ;
    freopen ( "apm.out" , "w" , stdout ) ;
    scanf ( "%ld %ld" , &n , &m ) ;
    for ( long i = 1 ; i <= m ; ++ i )
        scanf ( "%ld %ld %ld\n" , &a [ i ] . x , &a [ i ] . y , &a [ i ] . cost ) ;
    for ( long i = 1 ; i <= n ; ++ i )
        r [ i ] = i ;
    sort (a + 1 , a + m + 1 , cmp ) ;
    for ( long i = 1 ; i <= m ; ++ i )
    {
        xi = find ( a [ i ] . x ) ;
        yi = find ( a [ i ] . y ) ;
        if ( xi != yi && num <= n - 1 )
        {
            long  k ;
            ++ num ;
            nr += a [ i ] . cost ;
            k = unite ( a [ i ] . x , a [ i ] . y ) ;
            c [ num ] = i ;
        }
    }
    printf ( "%ld\n" , nr ) ;
    printf ( "%ld\n" , num ) ;
    for ( long i = 1 ; i <= num ; ++ i )
        printf ( "%ld %ld\n" , a [ c [ i ] ] . x , a [ c [ i ]  ] . y ) ;
    return 0 ;
}