#include <fstream>
#include <algorithm>

using namespace std;

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

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

bool cmp(int a, 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 <= n; i++)
        tt[i]=i;
    for (i = 1; i <= m; i++)
        f >> x[i] >> y[i] >> c[i], ind[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[X] = Y;
            s[++ns] = ind[i];
        }
    }
    g<<sm<<'\n' << n-1 << '\n';
    for (i=1; i < n; i++)
        g << x[s[i]]<<' ' << y[s[i]] << '\n';
    return 0;
}