#include <fstream>
#include <map>

using namespace std;

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

struct A
{
    int x, y;
};

multimap < int, A > a;

int n, m, i, x, y, s, nr;
int t[200001], lg[200001];
A r[200001];

void citire();
void lipire();
bool acelasi();

int main()
{
    citire();
    for ( i = 1 ; i <= n ; i++ ) t[i] = i;
    while ( a.empty() == 0 )
    {
        x = a.begin() -> second.x;
        y = a.begin() -> second.y;
        if ( acelasi() == 0 )
        {
            nr++;
            s += a.begin() -> first;
            r[nr] = { x, y };
            lipire();
        }
        a.erase ( a.begin() );
    }

    fout << s << '\n' << nr << '\n';
    for ( i = 1 ; i <= nr ; i++ ) fout << r[i].x << ' ' << r[i].y << '\n';

    return 0;
}

void citire()
{
    int i, x, y, z;

    fin >> n >> m;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> z;
        if ( x > y ) swap ( x, y );
        a.insert ( { z, { x, y } } );
    }
}

bool acelasi()
{
    int cx = x, cy = y;

    while ( t[cx] != cx ) cx = t[cx];
    while ( t[cy] != cy ) cy = t[cy];

    if ( cx == cy ) return 1;
    return 0;
}

void lipire()
{
    int cx = x, ccx = x, cy = y, ccy = y;

    while ( t[cx] != cx ) cx = t[cx];
    while ( t[cy] != cy ) cy = t[cy];

    if ( lg[cx] >= lg[cy] )
    {
        t[cy] = cx;
        while ( t[x] != x ) x = t[x], t[ccx] = cx, ccx = x;
        while ( t[y] != y ) y = t[y], t[ccy] = cx, ccy = y;
        if ( lg[cx] == lg[cy] ) lg[cx]++;
    }
    else
    {
        t[cx] = cy;
        while ( t[x] != x ) x = t[x], t[ccx] = cy, ccx = x;
        while ( t[y] != y ) y = t[y], t[ccy] = cy, ccy = y;
    }
}