#include <fstream>
#include <vector>
#include <algorithm>

using namespace std ;

ofstream fout ( "apm.out" ) ;

int N , M , TT[200005] , cost ;
struct edge
{
    int x ;
    int y ;
    int cost ;
} ;
vector < edge > APM , G ;

bool compare_test ( struct edge a , struct edge b )
{
    return a.cost < b.cost ;
}

int father ( int node )
{
    while ( node != TT[node] )
        node = TT[node] ;
    return node ;
}

void read()
{
    freopen ( "apm.in" , "r" , stdin ) ;
    scanf ( "%d %d" , &N , &M ) ;
    edge data ;
    for ( int i = 1 ; i <= M ; i++ )
    {
        scanf ( "%d %d %d" , &data.x , &data.y , &data.cost ) ;
        G.push_back(data) ;
    }
}

int main()
{
    int x , y ;
    read() ;
    for ( int i = 1 ; i <= N ; i++ )
        TT[i] = i ;
    sort ( G.begin() , G.end() , compare_test ) ;
    for ( vector < edge > :: iterator it = G.begin() ; it != G.end() ; ++it )
    {
        x = father ( it->x ) ;
        y = father ( it->y ) ;
        if ( x != y )
        {
            cost += it->cost ;
            TT[x] = y ;
            APM.push_back(*it) ;
        }
    }
    fout << cost << '\n' ;
    fout << N - 1 << '\n' ;
    for ( vector < edge > :: iterator it = APM.begin() ; it != APM.end() ; ++it )
        fout << it->x << ' ' << it->y << '\n' ;
    return 0;
}