#include <fstream>
#include <algorithm>
using namespace std;

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

int n, m, i, p, x, y, sefx, sefy, suma, sef[200001];

struct ura
{
    int x, y, val;
} muchie[200002];

struct solutie
{
    int x,y;
} sol[200001];

int sefsuprem( int i )
{
    if ( sef[i] == i )
        return i;
    return sef[i] = sefsuprem( sef[i] );
}

bool sortare (ura a, ura b)
{
    return a.val> b.val;
}

int main()
{
    cin>> n>> m;
    for( i = 1; i <= m; i++ )
        cin >> muchie[i].x >> muchie[i].y >> muchie[i].val;

    for( i = 1; i <= n; i++ )
        sef[i] = i;

    sort( muchie, muchie+ m, sortare );

    p = i = 1;
    while( p <= n-1 )
    {
        x = muchie[i].x;
        y = muchie[i].y;
        sefx = sefsuprem(x);
        sefy = sefsuprem(y);

        if( sefx != sefy )
        {
            sef[sefy] = sefx;
            sol[p].x = x;
            sol[p].y = y;
            p++;
            suma += muchie[i].val;
        }
        i++;
    }

    cout<< suma << '\n';
    cout<< n - 1 << '\n';

    for( i = 1; i < n ; i++ )
        cout << sol[i].x << ' ' << sol[i].y << '\n';
    return 0;
}