#include <fstream>
#include <algorithm>

using namespace std;

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

struct elem {
    int x, y, cost;
} v[400001];

int n, m, Min, pozMin, sol [100001], cost, T[100001], k;

int cmp (const elem a, const elem b) {
    return a.cost <= b.cost;
}

int rad (int nod) {
    while (T[nod] > 0) {
        nod = T[nod];
    }
    return nod;
}

int main () {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }

    sort (v + 1, v + m + 1, cmp);

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

    for (int i = 1; i <= m; i++) {
        int rx, ry;
        rx = rad (v[i].x);
        ry = rad (v[i].y);
        if (rx == ry)
            continue;
        if (rx != ry) {
            if (T[rx] < T[ry]) {
                T[rx] += T[ry];
                T[ry] = rx;
            }
            else {
                T[ry] += T[rx];
                T[rx] = ry;
            }
        }
        sol[++k] = v[i].x;
        sol[++k] = v[i].y;
        cost += v[i].cost;
    }

    fout << cost << "\n" << k / 2 << "\n";
    for (int i = 1; i <= k; i += 2) {
        fout << sol[i] << " " << sol[i + 1] << "\n";
    }




    return 0;
}