#include <fstream>
#include <algorithm>

#define IN "apm.in"
#define OUT "apm.out"

const int MAX = 400014 ;
const int MAX2 = 200014 ;

using namespace std;

struct nos{
    int a , b ;
    int cost ;
    bool viz ;
}; nos v [ MAX ];

int tata [ MAX2 ] , rang [ MAX2 ] ;

bool cmp ( nos a , nos b ) ;

int stramos ( int nod );
void unire ( int nod1 , int nod2 ) ;

int main( )
{
    ifstream fin ( IN ) ;
    ofstream fout ( OUT ) ;
    int n , m , bani = 0 ;
    fin >> n >> m ;
    for ( register int i = 1 ; i <= m ; ++ i )
        fin >> v [ i ].a >> v [ i ].b >> v [ i ].cost ;
    sort ( v + 1 , v + m + 1 , cmp ) ;
    for ( register int i = 1 ; i <= n ; ++ i ){
        tata [ i ] = i ;
        rang [ i ] = 1;
    }
    for ( register int i = 1 ; i <= m ; ++ i ){
        int tata_x = stramos ( v [ i ].a ) ;
        int tata_y = stramos ( v [ i ].b ) ;
        if ( tata_x != tata_y ){
            unire( tata_x , tata_y ) ;
            bani += v [ i ].cost ;
            v [ i ].viz = true ;
        }
    }
    fout << bani << '\n' << n - 1 << '\n' ;
    for ( register int i = 1 ; i <= m ; ++ i )
        if ( v [ i ].viz == true )
            fout << v [ i ].a << ' ' << v [ i ].b << '\n' ;
    return 0;
}

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

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

void unire ( int nod1 , int nod2 ){
    if ( rang [ nod1 ] >= rang [ nod2 ] ){
        tata [ nod2 ] = nod1 ;
        rang [ nod1 ] += rang [ nod2 ] ;
    }
    else{
        tata [ nod1 ] = nod2 ;
        rang [ nod2 ] += rang [ nod1 ] ;
    }
}