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

using namespace std;

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

vector < pair < int , pair <int,int> > > vect ;

struct muchie
{
    int x ; int y ;
};

muchie muchii[400005] ;

int n , m , i , x , y , c , nr , leg[200005] ;
long long suma ;

int cnx ( int vf )
{
    if ( leg[vf] != vf )
    {
        leg[vf] = cnx ( leg[vf] ) ;
    }

    return leg[vf] ;
}

int main()
{
    fin >> n >> m ;

    for ( i = 1 ; i <= m ; i ++ )
    {
        fin >> x >> y >> c ;

        vect.push_back ( make_pair ( c , make_pair ( x , y ) ) ) ;
    }

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

    for ( i = 1 ; i <= n ; i ++ )
    {
        leg[i] = i ;
    }

    for ( i = 0 ; i < vect.size() ; i ++ )
    {
        x = vect[i].second.first ;
        y = vect[i].second.second ;
        c = vect[i].first ;

        if ( cnx (x) != cnx (y) )
        {
            suma += c ;
            leg[leg[y]] = leg[x] ;
            nr ++ ;
            muchii[nr].x = x ; muchii[nr].y = y ;
        }
    }

    fout << suma << "\n" << nr << "\n" ;

    for ( i = 1 ; i <= nr ; i ++ )
    {
        fout << muchii[i].x << " " << muchii[i].y << "\n" ;
    }

    return 0;
}