#include <bits/stdc++.h>
using namespace std;

void file_in(string name) {
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
}

const int N = 200200;
const int M = 400400;
vector<int> t( N, 0 ), nr( N, 1 );

struct muchie {
    int from, to, cost;
};

bool cmp( muchie e1, muchie e2 ) {
    return e1.cost < e2.cost;
}

muchie edges[M];

int radacina( int x ) {
    if( t[x] == 0 ) 
        return x;

    t[x] = radacina( t[x] );
    return t[x];
}

void reuniune( int x, int y ) {
    int rx = radacina( x ), ry = radacina( y );

    if( nr[rx] < nr[ry] ) {
        t[rx] = ry;
        nr[ry] += nr[rx];
    } else {
        t[ry] = rx;
        nr[rx] += nr[ry];
    }
}

bool interogare( int x, int y ) {
    return ( radacina( x ) == radacina( y ) );
}

int main(  ) {
    file_in( "apm" );

    int n, m;
    scanf( "%d%d", &n, &m );

    vector<int> used_edges_idx;

    for( int i = 0; i < m; i++ ) {
        scanf( "%d%d%d", &edges[i].from, &edges[i].to, &edges[i].cost );
    }

    sort( edges, edges + m, cmp );

    // for( int i = 0; i < m; i++ )
    //     printf( "%d %d %d \n", edges[i].from, edges[i].to, edges[i].cost );

    long long cost_total = 0, k = 0;

    for( int i = 0; i < m; i++ ) {
        if( interogare( edges[i].from, edges[i].to ) )
            continue;

        k++;
        cost_total += edges[i].cost;
        reuniune( edges[i].from, edges[i].to );
        used_edges_idx.push_back(i);
    }

    printf("%d\n%d\n", cost_total, k);

    for( int sz = 0; sz < k; sz++ )
        printf( "%d %d\n", edges[used_edges_idx[sz]].to, edges[used_edges_idx[sz]].from );
}