#include <fstream>
#include <algorithm>
#include <vector>
#define pb push_back

using namespace std ;

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

const int NR = 200001 ;

vector < pair < int , int > > stiva ;

int TT [ NR ] ;
int GR [ NR ] ;


int find_root ( int x )
{
    int root ;

    for ( root = x ; TT [ x ] != x ; x = TT[ x ] , root = x ) ;

    for ( ; root != TT[ x ] ; )
    {
        int y = TT [ x ] ;
        TT [ x ] = root ;
        x = y ;
    }
    return root ;
}

void unite ( int x , int y )
{
    if ( GR [ x ] > GR [ y ] )  TT [ y ] = x ;
    else                        TT [ x ] = y ;
    if ( GR [ x ] == GR [ y ] )  GR [ y ] ++ ;
}

struct muchie
{
    int x , y ;
    long long cost ;
}v [ NR << 1 ];

int n , m ;

bool cmp ( muchie i , muchie j )
{
    return ( i.cost < j.cost ) ;
}

int main ()
{
    f >> n >> m ;
    for ( int i = 1 ; i <= m ; ++ i )   f >> v [ i ].x >> v [ i ].y >> v [ i ].cost ;

    sort ( v + 1 , v + m + 1 , cmp ) ;

    for ( int i = 1 ; i <= n ; ++ i )   TT [ i ] = i , GR [ i ] = 1;
    long long s = 0 ;
    for ( int i = 1 , cnt = 0 ; cnt < n - 1 ; i ++ )
    {
        int a = find_root( v [ i ].x ) , b = find_root( v [ i ].y ) ;
        if ( a != b )
            cnt ++ , unite ( a , b ) , s += v [ i ].cost ;
            stiva.pb ( make_pair ( v [ i ].y , v [ i ].x ) ) ;
    }

    g << s << "\n" << n - 1 << "\n" ;
    for ( size_t i = 0 ; i <stiva.size() ; ++ i )
        g << stiva[ i ].first << " " << stiva [ i ].second << "\n" ;
}