#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const char iname[] = "apm.in";
const char oname[] = "apm.out";
ifstream fin(iname);
ofstream fout(oname);
int n , m , comp[ 200010 ] , suma , i , j;
struct muchii
{
    int x , y , cost;
};
vector < muchii > v , sol;
struct cmp
{
	bool operator() ( const muchii &a , const muchii &b ) const
	{
		if ( a.cost < b.cost ) return 1;
		return 0;
	}
};
inline int cauta ( int x )
{
    int r , y;
    r = x;
    while ( comp[ r ] > 0 )
        r = comp[ r ];
    while ( comp[ x ] > 0 )
    {
        y = comp[ x ];
        comp[ x ] = r;
        x = y;
    }
    return r;
}
inline void uneste ( int x , int y )
{
    if ( comp[ x ] < comp[ y ] )
    {
        comp[ x ] += comp[ y ];
        comp[ y ] = x;
    }
    else
    {
        comp[ y ] += comp[ x ];
        comp[ x ] = y;
    }
}
int main()
{
	fin >> n >> m;
	muchii aux;
	for ( i = 1; i <= m; i++ )
    {
        fin >> aux.x >> aux.y >> aux.cost;
        v.push_back( aux );
    }
	sort( v.begin() , v.end() , cmp() );
    int n1 , nrm , x , y , cost;
    n1 = n - 1;
    for ( i = 1; i <= n; i++ )
        comp[ i ] = -1;
    vector <muchii> :: iterator it , final;
    it = v.begin();
    final = v.end();
    nrm = 0;
    while ( nrm != n1 && it != final )
    {
        aux = *it;
        ++it;
        x = aux.x;
        y = aux.y;
        cost = aux.cost;
        if ( cauta( x ) != cauta( y ) ) // daca nu sunt uneste multimile din care fac parte x si y atunci le unesc
        {
            nrm++;
            uneste( cauta( x ) , cauta( y ) );
            suma += cost;
            sol.push_back( aux );
        }
    }
	fout << suma << "\n";
    fout << sol.size() << "\n";
    for ( it = sol.begin(); it!=sol.end(); ++it )
    {
        aux = *it;
		fout << aux.x << " " << aux.y << "\n";
    }
    return 0;
}