/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on December 22, 2009, 9:00 AM
 */
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
#define pb push_back

/*
 * 
 */
using namespace std;
struct vertex
{
    int info;
    vertex* next;
} **F, **L;
typedef vertex* list;
inline void push( list& f, int x )
{
    list q=new vertex;
    q->info=x;
    q->next=f;
    f=q;
}
bool find( list f1, list f2 )
{
    for( ; f1->next || f2->next; )
    {
        if( f1->next )
            f1=f1->next;
        if( f2->next )
            f2=f2->next;
    }
    return f1 == f2;
}
struct cost
{
    int x, y, r;
};
inline istream& operator>>( istream& in, cost& A )
{
    in>>A.x>>A.y>>A.r;
}
inline ostream& operator<<( ostream& out, cost A )
{
    out<<A.x<<' '<<A.y<<'\n';
}
inline bool cmp( cost A, cost B )
{
    return A.r < B.r;
}
vector<cost> v, apm;
int main(int argc, char** argv)
{int n, m, i, s=0;
    ifstream in("apm.in");
    in>>n>>m;
    F=(list*)calloc( n, sizeof(vertex) );
    L=(list*)calloc( n, sizeof(vertex) );
    copy( istream_iterator<cost>(in), istream_iterator<cost>(), back_inserter(v) );
    sort( v.begin(), v.end(), cmp );
    for( i=0; i < n; ++i )
    {
        push( F[i], i );
        L[i]=F[i];
    }
    for( i=0; i < m && n; ++i )
        if( !find( F[v[i].x-1], F[v[i].y-1]) )
        {apm.pb(v[i]); s+=v[i].r;
            if( F[v[i].x-1] == L[v[i].x-1] )
                F[v[i].x-1]->next=L[v[i].x-1]->next=F[v[i].y-1];
            else L[v[i].x-1]->next=F[v[i].y-1];
            L[v[i].x-1]=L[v[i].y-1];
            F[v[i].y-1]=F[v[i].x-1];

        }
    ofstream out("apm.out");
    out<<s<<' '<<apm.size()<<'\n';
    copy( apm.begin(), apm.end(), ostream_iterator<cost>(out) );
    return (EXIT_SUCCESS);
}