/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on December 21, 2009, 2:54 PM
 */
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
#define pb push_back

/*
 * 
 */
using namespace std;
struct vertex
{
    int x, y, c;
};
vector<int> father;
vector< vertex > v, apm;
inline bool cmp( vertex A, vertex B )
{
    if( A.c == B.c )
    {
        if( A.x == B.x )
            return A.y < B.y;
        return A.x < B.x;
    }
    return A.c < B.c;
}
inline istream& operator>>( istream& in, vertex& A )
{
    in>>A.x>>A.y>>A.c;
    return in;
}
inline ostream& operator<<( ostream& out, vertex A )
{
    out<<A.x<<' '<<A.y;
    return out;
}
int main()
{int n, m, i, j, s=0, init, maxim;
    ifstream in("apm.in");
    in>>n>>m;
    copy( istream_iterator<vertex>(in), istream_iterator<vertex>(), back_inserter(v) );
    father.resize(n+1);
    for( i=1; i <= n; ++i )
        father[i]=i;
    sort( v.begin(), v.end(), cmp );
    for( i=0, m=v.size(); i < m ; ++i )
       if( father[v[i].x] != father[v[i].y] )
       {
           s+=v[i].c;
           apm.pb( v[i] ); //put it in
           init=min( father[v[i].x], father[v[i].y] );
           maxim=max( father[v[i].x], father[v[i].y] );
           for( j=1; j <= n; ++j )
               if( maxim == father[j] )
                   father[j]=init;
       }
    ofstream out("apm.out");
    out<<s<<' '<<apm.size()<<'\n';
    copy( apm.begin(), apm.end(), ostream_iterator<vertex>(out, "\n") );
    return 0;
}