#include <fstream>
#include <algorithm>

using namespace std;

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

int x[400005], y[400005], c[400005], ind[400005], tt[100005], n, m, i, ns, X, Y, vs[210005];
long long sm;

bool cmp(const int &a, const int &b) {
    return c[a] < c[b];
}

int update(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 <= m; i++) {
        f >> x[i] >> y[i] >> c[i];
        ind[i] = tt[i] = i;
    }
    sort(ind+1,ind+m+1,cmp);

    for (i = 1; i <= m; i++) {
        X = update(x[ind[i]]), Y = update(y[ind[i]]);
        if (X != Y) {
            sm += c[ind[i]];
            tt[update(x[ind[i]])] = update(y[ind[i]]);
            vs[++ns] = ind[i];
        }
    }
    g<<sm<<'\n' << n-1 << '\n';
    for (i = 1; i < n; i++)
        g << x[vs[i]] << ' ' << y[vs[i]]<<'\n';
    return 0;
}