#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std ;

ifstream f ( "apm.in" ) ;
ofstream g ( "apm.out" ) ;

const int NR = 400005 ;

vector < int > v ;

int x [ NR ] , y [ NR ] , c [ NR ] ;
int gr [ NR ] , ind [ NR ] , n , m , ans , cnt ;

bool cmp ( int x , int y )
{
    return c [ x ] < c [ y ] ;
}

int grupa ( int x )
{
    if ( gr [ x ] == x )    return x ;
    gr [ x ] = grupa ( gr [ x ] ) ;
    return gr [ x ] ;
}

void reuniune ( int x , int y )
{
    gr [ grupa ( x ) ] = grupa ( y ) ;
}


int main ( )
{
    f >> n >> m ;
    for ( int i = 1 ; i <= m ; ++ i )
    {
        f >> x [ i ] >> y [ i ] >> c [ i ] ;
        gr [ i ] = i ; ind [ i ] = i ;
    }
    sort ( ind + 1 , ind + m + 1 , cmp ) ;

    for ( int i = 1 ; i <= m ; ++ i )
    {
        if ( grupa ( x [ ind [ i ] ] ) != grupa ( y [ ind [ i ] ] )  )
        {
            ans += c [ ind [ i ] ] ; reuniune ( x [ ind [ i ] ] , y [ ind [ i ] ] ) ;
            v.push_back( ind [ i ] )  ;
            ++ cnt ;
            if ( cnt == n - 1 ) break ;
        }
    }
    g << ans << "\n" ;
    g << n - 1 << "\n" ;
    for ( unsigned i = 0 ; i < n - 1 ; ++ i )
    g <<  x [ v [ i ] ]  << " " << y [ v [ i ] ]  << "\n" ;
}