#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

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

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;

    vector<grf> apm;

    for (int i = 0; i < m; i++) {
        if (Reprez(graf[i].x) != Reprez(graf[i].y)) {
            Reuneste(graf[i].x, graf[i].y);
            apm.push_back(graf[i]);
            cost += graf[i].cost;
            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;
}