#include <fstream>
#include <algorithm>
#include <vector>

const int N_MAX = 200000;
const int M_MAX = 400000;

struct muchie {
    int x;
    int y;
    int cost;
};
int n, m;
muchie muchii[M_MAX];
int grupa[N_MAX + 1];
int cost_minim = 0;
std::vector<muchie> arbore_cost_minim = std::vector<muchie>();

bool cmp_muchii(muchie a, muchie b) {
    if (a.cost == b.cost) {
        int min_a = std::min(a.x, a.y);
        int max_a = a.x + a.y - min_a;
        int min_b = std::min(b.x, b.y);
        int max_b = b.x + b.y - min_b;
        if (min_a == min_b) {
            return max_a < max_b;
        }
        return min_a < min_b;
    }
    return a.cost < b.cost;
}

int gaseste_radacina(int nod) {
    if (grupa[nod] == nod) {
        return nod;
    }
    grupa[nod] = gaseste_radacina(grupa[nod]);
    return grupa[nod];
}

void reuniune(int nod_a, int nod_b) {
    int radacina_a = gaseste_radacina(nod_a);
    int radacina_b = gaseste_radacina(nod_b);
    if (radacina_a > radacina_b) {
        grupa[radacina_a] = grupa[radacina_b];
    }
    else if (radacina_a < radacina_b) {
        grupa[radacina_b] = grupa[radacina_a];
    }
}

int main() {
    std::ifstream in("apm.in");
    in >> n >> m;
    for (int j = 0; j < m; j ++) {
        in >> muchii[j].x >> muchii[j].y >> muchii[j].cost;
    }
    in.close();
    for (int i = 1; i <= n; i ++) {
        grupa[i] = i;
    }
    std::sort(muchii, muchii + m, cmp_muchii);

    for (int j = 0; j < m; j ++) {
        if (grupa[muchii[j].x] == grupa[muchii[j].y]) {
            continue;
        }
        cost_minim += muchii[j].cost;
        arbore_cost_minim.push_back(muchii[j]);
        reuniune(muchii[j].x, muchii[j].y);
    }

    std::ofstream out("apm.out");
    out << cost_minim << '\n';
    out << arbore_cost_minim.size() << '\n';
    for (auto much: arbore_cost_minim) {
        out << much.x << ' ' << much.y << '\n';
    }

    return 0;
}