#include <iostream>
#include <cstdlib>
#include <fstream>


#define ll long long
#define pb push_back

using namespace std;

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

const int EDGELIM = 4498502;

struct edgeS
{
    int x, y, l;
};

int N, M;
edgeS edge[EDGELIM];
bool res[EDGELIM];


int compar( const void* a, const void* b )
{
    edgeS e1 = *(edgeS*)a;
    edgeS e2 = *(edgeS*)b;

    if( e1.l < e2.l ) return -1;
    if( e1.l > e2.l ) return 1;
    return 0;
}



int parent[EDGELIM];
int rang[EDGELIM];

//*/
int findParent( int nod )
{
    if( parent[nod] == nod )
        return nod;

    parent[nod] = findParent( parent[nod] );
    return parent[nod];
}

bool join( int x, int y )
{
    int px = findParent( x );
    int py = findParent( y );

    if( px == py )
        return 0;

    if( rang[px] > rang[py] )
    {
        rang[py] += rang[px];
        parent[px] = py;
    }
    else// if( rang[py] > rang[px] )
    {
        rang[px] += rang[py];
        parent[py] = px;
    }


    return 1;
}
//*/



int main()
{
    fin >> N >> M;
    for( int i = 0; i < M; ++i )
    {
        fin >> edge[i].x >> edge[i].y >> edge[i].l;
    }

    qsort( edge, M, sizeof( edgeS ), compar );

    for( int i = 1; i <= N; ++i )
        parent[i] = i;


    int nr = 0;
    ll mst = 0;
    for( int i = 0; i < M && nr < N; ++i )
    {
        bool add = join( edge[i].x, edge[i].y );

        if( add )
            res[i] = 1;

        nr += add;
        mst += add * edge[i].l;
    }

    fout << mst << "\n";
    fout << N - 1 << "\n";

    for( int i = 0; i < M; ++i )
    {
        if( res[i] )
        {
            fout << edge[i].x << " " << edge[i].y << "\n";
        }
    }

    return 0;
}