#include <fstream>
#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" << n - 1 << "\n" ;
    for ( unsigned i = 0 ; i < n - 1 ; ++ i )
    g <<  x [ v [ i ] ]  << " " << y [ v [ i ] ]  << "\n" ;
    return 0 ;}