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

#define NMAX 200005
#define MMAX 400005

#define pb push_back
#define mp make_pair
#define cost first
#define nod1 second.first
#define nod2 second.second

using namespace std;

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

int N, M, x, y, cost, Pd[NMAX], i, CostAPM, NrMuchii;
pair< int, pair< int, int > > Muchii[MMAX];
vector< pair< int, int > > Sol;

inline int Grup( int Nod )
{
    if( Pd[Nod] == Nod ) return Nod;

    Pd[Nod] = Grup( Pd[Nod] );
    return Pd[Nod];
}

int main()
{
    in >> N >> M;
    for( i = 0; i < M; i++ )
    {
        in >> x >> y >> cost;
        Muchii[i] = mp( cost, mp( x, y ) );
    }

    sort( Muchii, Muchii+M );

    for( i = 1; i <= N; i++ ) Pd[i] = i;
    CostAPM = 0;

    for( i = 0; i < M; i++ )
        if( Grup( Muchii[i].nod1 ) != Grup( Muchii[i].nod2 ) )
        {
            Pd[ Grup( Muchii[i].nod1 ) ] = Pd[ Grup( Muchii[i].nod2 ) ];

            CostAPM += Muchii[i].cost;
            Sol.pb( mp( Muchii[i].nod1, Muchii[i].nod2 ) );
        }

    out << CostAPM << '\n' << Sol.size() << '\n';
    for( vector< pair< int, int > >::iterator it = Sol.begin(); it != Sol.end(); it++ )
        out << (*it).first << ' ' << (*it).second << '\n';

    return 0;
}