#include <bits/stdc++.h>

using namespace std;

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

const int maxn = 2e5 + 5;
const int maxm = 4e5 + 5;

struct edge {
    int x, y, val;
    bool operator < (const edge &aux) const {
        return (this->val < aux.val);
    }
} v[maxm];

int n, m, dad[maxn];
bool chosen[maxm];

int father( int x ) {
    if (x == dad[ x ])
        return x;
    return dad[ x ] = father( dad[ x ] );
}

void join( int x, int y ) {
    int rx = father( x ), ry = father( y );
    dad[ rx ] = ry;
}

int main()
{
    fi >> n >> m;

    for (int i = 1; i <=  m; i++) {
        fi >> v[ i ].x >> v[ i ].y >> v[ i ].val;
    }

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

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

    int x, y, nr = 0, answer = 0;
    for (int i = 1; i <= m && nr < n-1; i++) {
        x = v[ i ].x;
        y = v[ i ].y;
        if (father(x) != father(y)) {
            chosen[ i ] = 1;
            answer += v[ i ].val;
            join( x, y );
            nr++;
        }
    }

    fo << answer << '\n' << nr << '\n';
    for (int i = 1; i <= m; i++)
        if (chosen[ i ])
            fo << v[ i ].x << " " << v[ i ].y << '\n';


    return 0;
}