#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int nmax = 200005;
struct edge {
    int x, y, c;
}e[nmax],sol[2*nmax];
int x, y,c, n, m, i, X, Y, N,tt[nmax];
long long sm;

bool cmp(edge a, edge b) {
    return a.c < b.c;
}

int upd(int x) {
    int r = x, y;
    while (tt[r]!=r) r = tt[r];
    while (tt[x]!=x) {
        y = tt[x];
        tt[x] = r;
        x = y;
    }
    return r;
}

int main() {
    f >> n >> m;
    for (i = 1; i <= n; i++)
        tt[i] = i;

    for (i = 1; i <= m; i++) {
        f >> x >> y >> c;
        e[i] = {x,y,c};
    }
    sort(e+1, e+m+1, cmp);
    for (i = 1; i <= m; i++) {
        x = e[i].x, y = e[i].y;
        X = upd(x), Y = upd(y);
        if (X != Y) {
            sm += e[i].c;
            tt[X] = Y;
            sol[++N] = {x,y,100};
        }
    }
    g << sm << '\n' << N << '\n';
    for (i = 1; i <= N; i++)
        g << sol[i].x << ' ' << sol[i].y << '\n';
}