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

using namespace std;

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


struct Muchie { // structura pentru a reptrezenta o mcuhie
    int u, v, cost;
};

// funcție de comparare pentru sortarea muchiilor
bool comparaMuchii(const Muchie& a, const Muchie& b) {
    return a.cost < b.cost;
}


void kruskal_varianta1(int n, vector<Muchie>& muchii) {
    sort(muchii.begin(), muchii.end(), comparaMuchii); // sortam muchiile (Complexitate: O(m log m)) 

    // vectorul de reprezentanți
    // r[i] = reprezentantul nodului i. Inițial fiecare nod este propriul reprezentant.
    // Complexitate: O(n) 
    vector<int> r(n + 1);
    for (int i = 1; i <= n; i++) {
        r[i] = i; 
    }

    vector<Muchie> apcm; // aici vom stoca muchiile arborelui rezultat
    int costTotal = 0;
    int muchiiSelectate = 0;

    // 3. Parcurgerea muchiilor sortate
    for (const auto& muchie : muchii) {
        int u = muchie.u;
        int v = muchie.v;

        // operația Reprez (Find) - Complexitate O(1) 
        // Verificăm dacă u și v sunt în componente diferite
        if (r[u] != r[v]) {  
            // adăugăm muchia în soluție
            apcm.push_back(muchie);
            costTotal += muchie.cost;
            muchiiSelectate++;

            // Operația Reuneste (Union) - Specifică Variantei 1
            // Complexitate O(n) per operație 
            // Trebuie să schimbăm reprezentantul tuturor nodurilor care au reprezentantul lui cu reprezentantul lui u.
            
            int reprezentantVechi = r[v];
            int reprezentantNou = r[u];

            for (int k = 1; k <= n; k++) {
                if (r[k] == reprezentantVechi) {
                    r[k] = reprezentantNou;
                }
            }

            // Dacă am selectat deja n-1 muchii, ne putem opri (optimizare) 
            if (muchiiSelectate == n - 1) 
                break;
        }
    }

    // Afișare rezultate
    // cout << "Costul total al APCM: " << costTotal << endl;
    // cout << "Muchiile selectate sunt: " << endl;
    // for (const auto& muchie : apcm) {
    //     cout << "(" << muchie.u << ", " << muchie.v << ") cost: " << muchie.cost << endl;
    // }
    out<<costTotal<< "\n";
    out << apcm.size() << "\n";
    for (const auto& muchie : apcm) {
        out << muchie.u << " " << muchie.v << "\n";
    }

}

int main() {
    // Exemplu de date de intrare (n noduri, m muchii)
    int n,m;
    fin>>n>>m;
    // vector<Muchie> muchii = {
    //     {1, 2, 6}, {1, 3, 1}, {1, 4, 5},
    //     {2, 3, 5}, {2, 5, 3},
    //     {3, 4, 5}, {3, 5, 6}, {3, 6, 4},
    //     {4, 6, 2},
    //     {5, 6, 6}
    // };
    int x,y,cost;
    vector<Muchie> muchii;
    for (int i = 0 ; i < m ; i++){
        fin>>x>>y>>cost;
        muchii.push_back({x,y,cost});
    }

    kruskal_varianta1(n, muchii);

    return 0;
}