#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

struct cel
{
    long long cost, x1, x2;
}v[800001];

cel sol[800001];
long long k, costk;

long long sef[400001];


long long cmp ( cel a, cel b )
{
    if ( a.cost > b.cost )
        return 0;
    return 1;
}

long long boss ( long long x )
{
    if ( sef[x] == x )
        return x;
    else return sef[x] = boss( sef[x] );
}

void unire ( long long x, long long y )
{
    sef[ boss(y) ] = boss (x);
}

signed main()
{
    long long n, m;
    f >> n >> m;
    for ( long long i = 1; i <= m; i ++ )
        f >> v[i].x1 >> v[i].x2 >> v[i].cost;
    sort ( v + 1, v + m + 1, cmp );
    for ( long long i = 1; i <= n; i ++ )
        sef[i] = i;
    for ( long long i = 1; i <= m && k < n - 1; i ++ )
    {
        cel c = v[i];
        if ( boss ( c.x1 ) == boss ( c.x2 ) )
            continue;
        else
        {
            unire ( c.x1, c.x2 );
            sol[++k] = c;
            costk += c.cost;
        }
    }
    g << costk << '\n' << k << '\n';
    for ( long long i = 1; i <= k; i ++ )
        g << sol[i].x1 << " " << sol[i].x2 << '\n';
    return 0;
}