#include <fstream>
#include <algorithm>
#include <vector>
#define N 200000
#define M 400000

using namespace std;

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

int sef[N + 1];
short cost[M + 1];
int n, m;

int x[N + 1], y[N + 1], index[N + 1], ans[N];

int sefSuprem( int a ) {
    if ( sef[a] == a )
        return a;
    return sef[a] = sefSuprem( sef[a] );
}

void reuniune( int a, int b ) {
    int sa, sb;

    sa = sefSuprem( a );
    sb = sefSuprem( b );

    sef[sa] = sb;
}

bool compare( int i1, int i2 ) {
    return cost[i1] < cost[i2];
}

int main() {
    fin >> n >> m;
    for ( int i = 1; i <= m; i ++ ) {
        fin >> x[i] >> y[i] >> cost[i];
        index[i] = i;
    }

    for ( int i = 1; i <= n; i ++ )
        sef[i] = i;

    sort( index + 1, index + m + 1, compare );

    int cnt = 1, c = 0;
    for ( int i = 1; i <= m; i ++ ) {
        if ( sefSuprem( x[index[i]] ) != sefSuprem( y[index[i]] ) ) {
            reuniune( x[index[i]], y[index[i]] );
            c += cost[index[i]];
            ans[cnt ++] = index[i];
        }
    }
    fout << c << "\n" << n - 1 << "\n";
    for ( int i = 1; i <= cnt - 1; i ++ )
        fout << x[ans[i]] << " " << y[ans[i]] << "\n";
    return 0;
}