//Complexitate: O(M log N), unde M este numărul de muchii și N este numărul de noduri

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

using namespace std;

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

class Graf {
private:
    int nrNoduri; // Numărul de noduri din graf
    vector<pair<int, pair<int, int>>> muchii; // Vector de muchii, fiecare cu formatul (cost, (nod1, nod2))

public:
    Graf(int nrNoduri);

    void citireMuchii(int nrMuchii);

    void kruskalAPM();

private:
    int reprezentant(int nod, vector<int> &tata);

    void uneste(int tataSursa, int tataDestinatie, vector<int> &tata, vector<int> &inaltime);
};

Graf::Graf(int nrNoduri) {
    this->nrNoduri = nrNoduri;
}

void Graf::citireMuchii(int nrMuchii) {
    int sursa, destinatie, cost;
    // Citirea muchiilor
    for (int i = 1; i <= nrMuchii; i++) {
        fin >> sursa >> destinatie >> cost;
        muchii.push_back({cost, {sursa, destinatie}});
    }
}

int Graf::reprezentant(int nod, vector<int> &tata) {
    // Funcție recursivă pentru a găsi reprezentantul (rădăcina) unui nod
    if (tata[nod] != nod)
        tata[nod] = reprezentant(tata[nod], tata); // Comprimare drum (path compression)
    return tata[nod];
}

void Graf::uneste(int tataSursa, int tataDestinatie, vector<int> &tata, vector<int> &inaltime) {
    // Unirea a două subarbori pe baza înălțimii
    if (inaltime[tataSursa] > inaltime[tataDestinatie]) {
        tata[tataDestinatie] = tataSursa;
    } else if (inaltime[tataSursa] < inaltime[tataDestinatie]) {
        tata[tataSursa] = tataDestinatie;
    } else {
        tata[tataDestinatie] = tataSursa;
        inaltime[tataSursa]++;
    }
}

void Graf::kruskalAPM() {
    vector<pair<int, int>> apm; // Muchiile care vor face parte din APM
    vector<int> tata(nrNoduri + 1); // Vector pentru părinți
    vector<int> inaltime(nrNoduri + 1, 0); // Vector pentru înălțimea arborilor
    int costTotal = 0;

    // Inițializare: fiecare nod este reprezentant pentru sine
    for (int i = 1; i <= nrNoduri; i++) {
        tata[i] = i;
    }

    // Sortăm muchiile crescător după cost
    sort(muchii.begin(), muchii.end());

    // Procesăm fiecare muchie
    for (auto &muchie: muchii) {
        int cost = muchie.first;
        int nod1 = muchie.second.first;
        int nod2 = muchie.second.second;

        // Găsim reprezentanții celor două noduri
        int tata1 = reprezentant(nod1, tata);
        int tata2 = reprezentant(nod2, tata);

        // Dacă nodurile nu fac parte din același arbore, le unim
        if (tata1 != tata2) {
            uneste(tata1, tata2, tata, inaltime);
            apm.push_back({nod1, nod2}); // Adăugăm muchia în APM
            costTotal += cost; // Adăugăm costul muchiei la costul total
        }
    }

    // Afișăm rezultatul
    fout << costTotal << "\n"; // Costul total al APM
    fout << apm.size() << "\n"; // Numărul de muchii din APM
    for (auto &muchie: apm) {
        fout << muchie.first << " " << muchie.second << "\n"; // Muchiile din APM
    }
}

int main() {
    int nrNoduri, nrMuchii;
    fin >> nrNoduri >> nrMuchii;

    Graf g(nrNoduri);
    g.citireMuchii(nrMuchii);
    g.kruskalAPM();

    fin.close();
    fout.close();
    return 0;
}