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

using namespace std;

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


struct Muchie { // structura pentru a reprezenta o muchie
    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_varianta2(int n, vector<Muchie>& muchii) {
    sort(muchii.begin(), muchii.end(), comparaMuchii); // sortam muchiile (Complexitate: O(m log m))

    // Inițializare structuri pentru Varianta 2 (Union-Find)
    // tata[i] = părintele nodului i (0 dacă i este rădăcină) 
    // h[i] = înălțimea arborelui cu rădăcina în i 
    vector<int> tata(n + 1, 0);
    vector<int> h(n + 1, 0);

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

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

        // Operația Reprez (Find) - Varianta 2
        // Determinăm rădăcina arborelui care conține u, respectiv v
        // Complexitate: O(log n) per operație (datorită optimizării prin înălțime) 
        
        int ru = u;
        while (tata[ru] != 0) {
            ru = tata[ru];
        }

        int rv = v;
        while (tata[rv] != 0) {
            rv = tata[rv];
        }

        // Verificăm dacă u și v sunt în componente diferite (rădăcini diferite)
        if (ru != rv) {  
            // adăugăm muchia în soluție
            apcm.push_back(muchie);
            costTotal += muchie.cost;
            muchiiSelectate++;

            // Operația Reuneste (Union) - Varianta 2 (Ponderată după înălțime)
            // Complexitate O(1) după ce am găsit reprezentanții
            // Arborele cu înălțimea mai mică devine subarbore al rădăcinii celuilalt 
            
            if (h[ru] > h[rv]) {
                tata[rv] = ru;
            } else {
                tata[ru] = rv;
                if (h[ru] == h[rv]) {
                    h[rv]++; // Crește înălțimea doar dacă arborii aveau înălțimi egale
                }
            }

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

    // Afișare rezultate
    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;

    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_varianta2(n, muchii);

    return 0;
}