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

void citire(std::vector<std::tuple<int, int, int> > &graf, int &n) {
    int m;
    int i, j, w;
    std::ifstream f("apm.in");
    f >> n >> m;
    while (m--) {
        f >> i >> j >> w;
        graf.emplace_back(i - 1, j - 1, w);
    }
    f.close();
}

// ARBORI - reprezentantul unei componente este radacina arborelui
// reuniune: radacina unui arbore devine fiu al radacinii celuilalt arbore (arborele cu H mai mic devine subarbore)
// O(mlogn)

int reprez(std::vector<int> &tata, const int i) {
    if (tata[i] == -1)
        return i;
    return tata[i] = reprez(tata, tata[i]); // buff compression pt. optimizare
}

void reuneste(std::vector<int> &tata, std::vector<int> &h, const int r1, const int r2) {
    if (h[r1] > h[r2])
        tata[r2] = r1;
    else {
        tata[r1] = r2;
        if (h[r1] == h[r2])
            h[r2] = h[r1] + 1;
    }
}

void kruskalArbori() {
    std::vector<std::tuple<int, int, int> > graf;
    int n;
    citire(graf, n);

    std::ranges::sort(graf, [](const std::tuple<int, int, int> &a, const std::tuple<int, int, int> &b) {
        return std::get<2>(a) < std::get<2>(b);
    });

    std::vector tata(n, -1), h(n, 0);
    int cost = 0;
    int nrMuchii = 0;
    std::vector<std::pair<int, int> > arbore;
    for (const auto &[i, j, w]: graf) {
        const int r1 = reprez(tata, i);
        if (const int r2 = reprez(tata, j); r1 != r2) {
            arbore.emplace_back(i, j);
            cost += w;
            if (++nrMuchii == n - 1)
                break;
            // Reunim arborii
            reuneste(tata, h, r1, r2);
        }
    }

    std::ofstream g("apm.out");
    g << cost << "\n" << nrMuchii << "\n";
    for (const auto &[i, j]: arbore)
        g << i + 1 << " " << j + 1 << "\n";
    g.close();
}

int main() {
    kruskalArbori();
    return 0;
}