#include <fstream>
#include <algorithm>

#define MAXN 200000
#define MAXM 400000

std::ifstream in( "apm.in" );
std::ofstream out( "apm.out" );

struct edges{ int x, y, cost; bool takenornot = false; };

int father[ MAXN + 1 ];
edges edg[ MAXM + 1 ];
int n, m;

bool compare_cost( edges a, edges b ){ return a.cost < b.cost; }

int find( int a )
{
    int fth = father[ a ];
    if( father[ fth ] != fth )
    {
        return father[ a ] = find( fth );
    }

    return fth;
}

int unionn( int a, int b )
{
    father[ find( a ) ] = find( b );
}

void input( )
{
    in >> n >> m;
    for( int i = 1; i <= n; i++ ){ father[ i ] = i; }

    for( int i = 1; i <= m; i++ )
    {
        in >> edg[ i ].x >> edg[ i ].y >> edg[ i ].cost;
    }

    std::sort( edg + 1, edg + m + 1, compare_cost );
}

void solve( )
{
    int edges_taken = 0, totalcost = 0, i = 1;
    while( i <= m && edges_taken < n - 1 )
    {
        int fatherx = find( edg[ i ].x ), fathery = find( edg[ i ].y );
        if( fatherx != fathery )
        {
            edges_taken++, edg[ i ].takenornot = true;
            totalcost += edg[ i ].cost;
            unionn( fatherx, fathery );
        }
        i++;
    }

    out << totalcost << '\n' << n - 1 << '\n';
    for( i = 1; i <= m; i++ )
    {
        if( edg[ i ].takenornot == true )
        {
            out << edg[ i ].x << " " << edg[ i ].y << '\n';
        }
    }
}

int main()
{
    input( );
    solve( );
    return 0;
}