#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

const int N = 200010;

int n, m, i, j, s, t[N], k, a[N], rx, ry;

struct apm{
    int x, y, c;
} v[2 * N];

bool cmp(apm x, apm y) {
    return x.c<y.c;
}

int rad(int x) {
    if(t[x] < 0)
        return x;
    return t[x] = rad(t[x]);
}

int main() {
    fin >> n >> m;
    for (i = 1; i <= n; ++i) {
        t[i] = -1;
    }
    for (i = 1; i <= m; ++i) {
        fin >> v[i].x >> v[i].y >> v[i].c;
    }
    sort(v + 1, v + m + 1, cmp);
    s = 0;
    for (i = 1; i <= m; ++i) {
        rx = rad(v[i].x);
        ry = rad(v[i].y);
        if (rx != ry) {
            s += v[i].c;
            a[++k] = i;
            if (t[rx] < t[ry]) {
                t[rx] += t[ry];
                t[ry] = rx;
            } else {
                t[ry] += t[rx];
                t[rx] = ry;
            }
        }
    }
    fout << s << "\n" << k << "\n";
    for (i = 1; i < n; ++i) {
        k = a[i];
        fout << v[k].x << ' ' << v[k].y << "\n";
    }
    return 0;
}