/* 
 * File:   main.cpp
 * Author: VirtualDemon
 *
 * Created on April 9, 2010, 7:46 PM
 */
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#include <algorithm>
#define oo 0x3f3f3f3f

/*
 * 
 */
using namespace std;
vector< int > f, r;
class pr
{
    int x, y, c;
    inline int find( int x )
    {
        int y, z;
        for( y=f[x]; y != f[y]; y=f[y] );
        for( ; x != f[x]; x=z )
        {
            z=f[x];
            f[x]=y;
        }
        return y;
    }
    inline void unite( int x, int y )
    {
        if( r[x] == r[y] )
        {
            if( x != y )
                f[y]=x;
            ++r[y];
        }
        else r[x]=r[y]=min( r[x], r[y] );
    }
public :
    pr( void ) : x(0), y(0), c(oo) { }
    pr( int _x, int _y, int _c ) : x(_x), y(_y), c(_c) { }
    inline bool operator<( const pr& z ) const
    {
        return c < z.c;
    }
    inline bool find( void )
    {
        int rx=find(x), ry=find(y);
        if( rx != ry )
        {
            unite( rx, ry );
            return true;
        }
        return false;
    }
    friend inline void add( int& x, const pr& y )
    {
       x+=y.c;
    }
    friend inline istream& operator>>( istream& in, pr& z )
    {
        in>>z.x>>z.y>>z.c;
        --z.x, --z.y;
        return in;
    }
    friend inline ostream& operator<<( ostream& out, const pr& z )
    {
        out<<(z.x+1)<<' '<<(z.y+1)<<'\n';
        return out;
    }
};
vector< pr > v, apm;
int main( void )
{
    int N, M, i, s=0;
    ifstream in( "apm.in" );
    in>>N>>M;
    for( i=0; i < N; ++i )
        f.push_back(i), r.push_back(1);
    copy( istream_iterator<pr>(in), istream_iterator<pr>(), back_inserter(v) );
    sort( v.begin(), v.end() );
    for( i=0; i < M; ++i )
    {
        if( v[i].find() )
        {
            apm.push_back(v[i]);
            add( s, v[i] );
            if( N == apm.size() )
                break;
        }
    }
    ofstream out( "apm.out" );
    out<<s<<'\n'<<v.size()<<'\n';
    copy( apm.begin(), apm.end(), ostream_iterator<pr>( out ) );
    return EXIT_SUCCESS;
}