#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) {
    if (r[u] != u)
        r[u] = Reprez(r[u]);
    return r[u];
}

void Reuneste(int u, int v) {
    int r1 = Reprez(u);
    int r2 = Reprez(v);
    if (r1 != r2) {
        if (r1 < r2)
            r[r2] = r1;
        else
            r[r1] = r2;
    }
}

int main() {

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

    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;

    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;
}