#include <fstream>
#include <algorithm>
#define MAX_M 400002
#define MAX_N 200002
using namespace std;

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

struct muchie
{
    int x, y, c;
};

int n, m, cost_apm, k, tata[ MAX_N ], grad[ MAX_N ], sol[ MAX_N ];
muchie v[ MAX_M ];

void citire()
{
    f >> n >> m;

    for ( int i = 1; i <= m; ++ i )
        f >> v[ i ].x >> v[ i ].y >> v[ i ].c;
}

void init()
{
    for ( int i = 1; i <= n; ++ i )
    {
        tata[ i ] = i;
        grad[ i ] = 1;
    }
}

int multime ( int x )
{
    if ( tata[ x ] != x )
       tata[ x ] = multime( tata[ x ] );

    return tata[ x ];
}

void unificare ( int a, int b )
{
    if ( grad[ a ] < grad[ b ] )
        tata[ a ] = b;

    else
    {
        tata[ b ] = a;
        if ( grad[ a ] == grad[ b ] )
            ++ grad[ a ];
    }
}

bool comp ( muchie a, muchie b )
{
    return a.c < b.c;
}

void afisare()
{
    g << cost_apm << endl << n - 1 << endl;

    for ( int i = 0; i < k; ++ i )
        g << v[ sol[ i ] ].x << " " << v[ sol[ i ] ].y << endl;
}

int main()
{
    citire();

    sort ( v + 1, v + m + 1, comp );

    init();

    int a, b;
    for ( int i = 1; i <= m && k < n; ++ i )
    {
        a = multime( v[ i ].x );
        b = multime( v[ i ].y );

        if ( a != b )
        {
            sol[ k ++ ] = i;
            cost_apm += v[ i ].c;
            unificare( a, b );
        }
    }

    afisare();
    return 0;
}