// kruskal
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_M = 400002;
const int MAX_N = 200002;

vector < int > sol;

int N, M, APM, comp[ MAX_N ], index[ MAX_M ], X[ MAX_M ], Y[ MAX_M ], C[ MAX_M ];

int cmp( int x, int y )
{
    return C[ x ] < C[ y ];
}

void read()
{
    int i;
    freopen( "apm.in", "r", stdin);
    scanf( "%d %d", &N, &M );
    for( i = 1; i <= M; ++i )
    {
        scanf( "%d %d %d", &X[ i ], &Y[ i ], &C[ i ] );
        index[ i ] = i;
    }
    fclose( stdin );
}

int group( int x )
{
    if( comp[ x ] == x)
        return x;
    comp[ x ] = group( comp[ x ] );
    return comp[ x ];
}

void solve()
{
    int i;

    for( i = 1; i <= N; ++i )
        comp[ i ] = i;
    for( i = 1; i <= M; ++i )
    {
        if( group( X[ index[ i ] ] ) != group( Y[ index[ i ] ] ) )
        {
            APM += C[ index[ i ] ];
            comp[ group( X[ index[ i ] ] ) ] = group( Y[ index[ i ] ] );
            sol.push_back( i );
        }
    }
}

void write()
{
    freopen( "apm.out", "w", stdout );
    int i;
    printf( "%d\n%d\n", APM, sol.size() );
    for( i = 0 ; i < sol.size(); ++i )
        printf("%d %d\n", X[ index[ sol[ i ] ] ], Y[ index[ sol[ i ] ] ]);
    fclose(stdout);
}

int main()
{
    read();
    std::sort( index + 1, index + M + 1, cmp);
    solve();
    write();
    return 0;
}