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

using namespace std;

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

int n, m, x, y, d, h[200002], t[200002], sum, nr;
vector<pair<int,pair<int, int> > >m1;
vector<pair<int,int> >m2;

int padre( int k )
{
    if( k == t[k] )
        return k;
    else return t[k] = padre( t[k] );
}

void reuniune( int x1, int x2 )
{
    int y1 = padre(x1);
    int y2 = padre(x2);

    if( h[y1] < h[y2] )
    {
        t[y1] = y2;
    }
    else if( h[y1] > h[y2] )
    {
        t[y2] = y1;
    }
    else
    {
        t[y2] = y1;
        h[y1] ++;
    }
}

int main()
{
    f >> n >> m;
    for( int i=1; i<=m; ++i )
    {
        f >> x >> y >> d;
        m1.push_back( make_pair( d, make_pair(x, y)));
    }

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

    sort( m1.begin(), m1.end() );

    vector<pair<int,pair<int,int> > >::iterator it = m1.begin();
    pair<int,pair<int,int> >p;

    while( nr < n-1 )
    {
        p = *it;
        x = p.second.first;
        y = p.second.second;
        d = p.first;

        int tx, ty;

        tx = padre(x);
        ty = padre(y);

        if( tx != ty )
        {
            nr++;
            sum += d;
            m2.push_back(make_pair(x, y));
            reuniune(tx, ty);
        }
        ++it;
    }

    g << sum << '\n' << n - 1 << '\n';

    for( vector<pair<int,int > >::iterator it = m2.begin(); it!=m2.end(); ++it )
        g << it->first << " " << it->second << '\n';

    return 0;
}