#include <algorithm>
#include <fstream>
#include <vector>
#include <tuple>
using namespace std;
	
ifstream fin( "apm.in" );	
ofstream fout( "apm.out" );
	
const int N = 200010;
int n, m, v[ N ], cost;
	
vector<tuple<int,int,int>> e;
vector<pair<int,int>> sol;

int getRoot( int nod ) { 
    if( v[ nod ] == nod )
        return nod;
    v[ nod ] = getRoot( v[ nod ] );
    return v[ nod ];
}

int main()
{
    fin >> n >> m;
    for( int i = 1; i <= n; i++ )
        v[ i ] = i;
	
    for( ; m; m-- ){
        int x, y, c;
        fin >> x >> y >> c;
        e.push_back( { c, x, y } );
    }
    sort( e.begin(), e.end() );

    for( auto it:e ) {
        int x, y, c;
        tie( c, x, y ) = it;
        int rx = getRoot( x );
        int ry = getRoot( y );
        if( rx != ry ) {
            v[ rx ] = ry;
            sol.push_back( { x, y } );
            cost += c;
        }
    }
    fout << cost << '\n' << n - 1 << '\n';
    for( auto it : sol )
        fout << it.first << ' ' << it.second << '\n';
    return 0;
}