#include <fstream>
#include <algorithm>

#define MAXN 200000
#define MAXM 400000

using namespace std;

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

struct edges{ int x, y, cost; };

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

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

int findd( int a )
{
    if( father[ a ] == a ) return a;
    else return father[ a ] = findd( father[ a ] );
}

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

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;
    }

    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 = findd( edg[ i ].x ), fathery = findd( edg[ i ].y );
        if( fatherx != fathery )
        {
            edges_taken++;
            totalcost += edg[ i ].cost;
            taken[ edges_taken ] = i;
            unionn( fatherx, fathery );
        }
        i++;
    }

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

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