/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 22, 2010, 2:19 PM
 */
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>

/*
 *
 */
using namespace std;
typedef unsigned int u;
struct vertex
{
    u x, y;
    int c;
};
inline istream& operator>>( istream& in, vertex& z )
{
    in>>z.x>>z.y>>z.c;
    return in;
}
inline ostream& operator<<( ostream& out, vertex z )
{
    out<<z.x<<' '<<z.y<<'\n';
    return out;
}
inline bool operator<( vertex A, vertex B )
{
    return A.c < B.c;
}
vector<u> father;
u find( u x )
{
    u y, z;
    for( y=x; y != father[y]; y=father[y] );
    for( ; x != father[x]; )
    {
        z=father[x];
        father[x]=y;
        x=z;
    }
    return y;
}
vector< vertex > v, apm;
int main()
{int s=0;
 u n, m, i, fx, fy;
    ifstream in("apm.in");
    in>>n>>m;
    copy( istream_iterator<vertex>(in), istream_iterator<vertex>(), back_inserter(v) );
    sort( v.begin(), v.end() );
    for( i=0; i < n; ++i )
        father.push_back(i);
    for( i=0; i < m; ++i )
    {
        fx=find( v[i].x );
        fy=find( v[i].y );
        if( fx != fy )
        {s+=v[i].c;
            father[fy]=fx;
            apm.push_back(v[i]);
            if( apm.size() == n-1 )
                break;
        }
    }
    ofstream out("apm.out");
    out<<s<<'\n'<<(n-1)<<'\n';
    copy( apm.begin(), apm.end(), ostream_iterator<vertex>(out) );
    return 0;
}