#include <cstdio>
#include <algorithm>
#include <vector>
#define NMAX 200009
using namespace std;

struct edge {
    int x, y, c;
    edge () {}
    edge (int _x, int _y, int _c) : x(_x), y(_y), c(_c) {}

    bool operator<(const edge& e) {
        return c < e.c;
    }
};

int N, M, cost, T[ NMAX ];
vector< edge > E,sol;


int djset(int x) {
    if (T[ x ] != x) {
        T[ x ] = djset( T[ x ] );
    }
    return T[ x ];
}

int reunion(int x, int y) {
    T[ djset(x) ] = djset( y );
}

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

    scanf("%d%d", &N, &M);
    while (M--) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        E.push_back( edge(x, y, c) );
    }

    sort(E.begin(), E.end());

    for (int i = 1; i <= N; ++i) {
        T[ i ] = i;
    }

    for (vector<edge>::iterator it =  E.begin(); it != E.end(); ++it) {
        int x = it->x, y = it->y, c = it->c;
        if (djset(x) != djset(y)) {
            reunion(x, y);
            cost += c;
            sol.push_back( *it );
            if (sol.size() == N - 1) {
                break;
            }
        }
    }

    printf("%d\n%d\n", cost, sol.size());
    for (vector<edge>::iterator it =  sol.begin(); it != sol.end(); ++it) {
        printf("%d %d\n", it->x, it->y);
    }

    return 0;
}