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

using namespace std;

ifstream fin( "apm.in" ); ofstream fout( "apm.out" );

const int nmax = 200000;
int ans;
int tata[ nmax + 1 ], grad[ nmax + 1 ];

struct muchie{
    int x, y, c;

    muchie() {}
    muchie( int _x, int _y, int _c ) : x( _x ), y( _y ), c( _c ) {}

    inline bool operator < ( const muchie &a ) const {
        return ( c < a.c );
    }
};
vector< muchie > g, sol;

int find_tata( int x ) {
    if ( x == tata[ x ] ) {
        return x;
    }
    return (tata[ x ] = find_tata( tata[ x ] ));
}
void kruskal() {
    ans = 0;
    sort( g.begin(), g.end() );

    for( vector< muchie >::iterator it = g.begin(); it != g.end(); ++ it ) {
        int ta = find_tata( it -> x ), tb = find_tata( it -> y );

        if ( ta != tb ) {
            sol.push_back( *it );
            ans += (it -> c);
            if ( grad[ ta ] < grad[ tb ] ) {
                grad[ tb ] += grad[ ta ];
                tata[ ta ] = tb;
            } else {
                grad[ ta ] += grad[ tb ];
                tata[ tb ] = ta;
            }
        }
    }
}
int main() {
    int n, m;
    fin >> n >> m;
    for( int i = 1; i <= n; ++ i ) {
        tata[ i ] = i;
        grad[ i ] = 1;
    }
    for( int i = 0; i < m; ++ i ) {
        int x, y, z;
        fin >> x >> y >> z;
        g.push_back( muchie( x, y, z ) );
    }

    kruskal();
    fout << ans << "\n" << n - 1 << "\n";
    for( vector< muchie >::iterator it = sol.begin(); it != sol.end(); ++ it ) {
        fout << (it -> x) << " " << (it -> y) << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}