#include <fstream>
#include <algorithm>

using namespace std;

struct muchii
{
    int x , y , cost ;
};

muchii q [ 400014 ] ;

int tata [ 200014 ] ;
int rang [ 200014 ] ;

bool cmp ( muchii a , muchii b )
{
    return a.cost < b.cost ;
}

int stramos ( int nod )
{
    int R = nod ;
    while ( R != tata [ R ] ) {
        R = tata [ R ] ;
    }
    while ( nod != tata [ nod ] ) {
        int aux = tata [ nod ] ;
        tata [ nod ] = R ;
        nod = aux ;
    }
    return R ;
}

inline void unite ( int x , int y )
{
    x = stramos( x ) ;
    y = stramos( y ) ;
    if ( x == y ) return ;
    if ( rang [ x ] > rang [ y ] ){
        rang [ x ] += rang [ y ] ;
        tata [ y ] = tata [ x ] ;
    }
    else {
        rang [ y ] += rang [ x ] ;
        tata [ x ] = tata [ y ] ;
    }
}

vector < pair < int , int > > M ;

ifstream cin ( "apm.in" ) ;
ofstream cout ( "apm.out" ) ;

int main()
{
    int n , m ;
    cin >> n >> m ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        tata [ i ] = i ;
        rang [ i ] = 1 ;
    }
    for ( int i = 1 ; i <= m ; ++ i ) {
        cin >> q [ i ].x >> q [ i ].y >> q [ i ].cost ;
    }
    sort ( q + 1 , q + m + 1 , cmp ) ;
    int APM = 0 ;
    for ( int i = 1 ; i <= m ; ++ i ) {
        if ( stramos ( q [ i ].x ) != stramos( q [ i ].y ) ) {
            APM += q [ i ].cost ;
            unite ( q [ i ].x , q [ i ].y ) ;
            M.push_back ( make_pair ( q [ i ].x , q [ i ].y ) ) ;
        }
    }
    cout << APM << '\n' ;
    cout << M.size ( ) << '\n' ;
    for ( auto x : M ) {
        cout << x.first << ' ' << x.second << '\n' ;
    }
    return 0;
}