/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

#include <bits/stdc++.h>

using namespace std;

ifstream fin ( "apm.in" ) ;
ofstream fout ( "apm.out" ) ;

const int MAX = 4e5 + 14 ;

int tata [ MAX ] ;
int rang [ MAX ] ;

struct muchii {
    int x , y , cost ;
    void sett ( int a , int b , int c )
    {
        x = a ;
        y = b ;
        cost = c ;
    }
};

muchii q [ MAX ] ;

struct cmp {
    bool operator ( ) ( const muchii &a , const muchii &b ) const
    {
        return a.cost < b.cost ;
    }
};

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

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 > > Edges ;

int main ( )
{
    int n , m ;
    fin >> n >> m ;
    for ( int i = 1 ; i <= m ; ++ i ) {
        int x , y , cost ;
        fin >> x >> y >> cost ;
        q [ i ].sett ( x , y , cost ) ;
    }
    sort ( q + 1 , q + m + 1 , cmp ( ) ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        tata [ i ] = i ;
        rang [ i ] = 1 ;
    }
    int APM = 0 ;
    for ( int i = 1 ; i <= m ; ++ i ) {
        if ( stramos ( q [ i ].x ) == stramos ( q [ i ].y ) ) {
            continue ;
        }
        unite ( q [ i ].x , q [ i ].y ) ;
        APM += q [ i ].cost ;
        Edges.push_back ( make_pair ( q [ i ].x , q [ i ].y ) ) ;
    }
    fout << APM << '\n' ;
    fout << n - 1 << '\n' ;
    for ( auto x : Edges ) {
        fout << x.first << ' ' << x.second << '\n' ;
    }
    return 0;
}