#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

#define NMAX 200005
#define MMAX 400005

struct muchie{
    int x, y, c;
} v[ MMAX ];

vector < pair < int, int > > sol;
int mini, parent[ NMAX ];

int radacina( int x );
void addMuchie( int x, int y, int c );
bool cmp( muchie a, muchie b );


int main()
{

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    int n, m, i, j, x, y, c;
    vector < pair < int, int > > :: iterator it;

    scanf("%d%d",&n,&m);
    for( i = 1; i <= m; ++i )
        scanf("%d%d%d",&v[ i ].x,&v[ i ].y,&v[ i ].c);

    sort( v + 1, v + 1 + m, cmp );

    for( i = 1; i <= n; ++i ) parent[ i ] = i;
    for( i = 1; i <= m; ++i ) addMuchie( v[ i ].x, v[ i ].y, v[ i ].c );

    printf("%d\n%d\n",mini,sol.size());
    for( it = sol.begin(); it != sol.end(); ++it ) printf("%d %d\n",it -> first,it -> second);


    return 0;

}

bool cmp( muchie a, muchie b ){
    return a.c < b.c;
}

int radacina( int x ){

    if( x == parent[ x ] ) return x;
    return radacina( parent[ x ] );

}

void addMuchie( int x, int y, int c ){

    int rx = radacina( x );
    int ry = radacina( y );

    if( rx == ry ) return ;
    mini += c;

    parent[ ry ] = rx;
    sol.push_back( { x, y } );

}