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

#define cost first
#define nod1 second.first
#define nod2 second.second
using namespace std;
int n,m,tat[200005],nsol,c,i,j,x,y;

vector < pair < int, pair < int, int > > > v ;
vector < pair < int, int > > sol;

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

int schimbtat( int x )
{

        if( x == tat[ x ] )
        {
            return x;
        }
        else
            return schimbtat( tat[ x ] );
}
int main()
{
    fin>>n>>m;
    for( i = 1; i <= n; i++ )
        tat[ i ] = i;
    for( i = 1; i <= m; i++ )
    {
        fin>>x>>y>>c;
        v.push_back( { c ,{ x , y } } );
    }
    sort( v.begin( ) , v.end( )  );
    c = 0;
    for( auto it : v )
    {
        if( schimbtat(  it.nod1  ) != schimbtat( it.nod2  ) )
        {
            sol.push_back( { it.nod1, it.nod2  } );
            tat[ max( schimbtat( it.nod1 ),schimbtat( it.nod2 ) ) ] = min ( schimbtat( it.nod1 ),schimbtat( it.nod2 ) );
            c += it.cost;
        }
    }

    fout<<c<<'\n';
    fout<<sol.size( )<<'\n';
    for( auto it:sol )
        fout<<it.second<<" "<<it.first<<'\n';
    return 0;
}