#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

//ifstream in("grafpond.in");
//ofstream out("grafpond.out");

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

int r[200001];
int n, m;


struct grf {
    int x;
    int y;
    int cost;
};

bool compare(grf j, grf i) {
    return (i.cost > j.cost);
}

int Reprez(int u) {
    return r[u];
}

void Reuneste(int u, int v) {
    int r1 = Reprez(u);
    int r2 = Reprez(v);
    for (int k = 1; k <= n; k++)
        if (r[k] == r2)
            r[k] = r1;
}

void afisare(grf graf[40001]) {

    for (int i = 0; i < m; i++) {
        cout << graf[i].x << " " << graf[i].y << " " << graf[i].cost;
        cout << endl;
    }

}

int main() {

    in >> n >> m;
    grf graf[400001];

    for (int i = 0; i < m; i++) {
        in >> graf[i].x >> graf[i].y >> graf[i].cost;
    }
    sort(graf, graf + m, compare);

    for (int i = 1; i <= n; i++)
        r[i] = i;

    int cost = 0;
    int nrmsel = 0;
    // afisare(graf);
    grf apm[290000];

    for (int i = 0; i < m; i++) {
        if (Reprez(graf[i].x) != Reprez(graf[i].y)) {
            Reuneste(graf[i].x, graf[i].y);
            cost += graf[i].cost;
            apm[nrmsel] = graf[i];
            nrmsel++;
            if (nrmsel == n - 1)
                break;
        }
    }
    out << cost << endl << nrmsel << endl;
    for (int i = 0; i < nrmsel; i++) {
        out << apm[i].x << " " << apm[i].y << endl;
    }
    return 0;
}