#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional> // Necesar pentru std::greater<>
using namespace std;

ofstream g("apm.out");

const int NMAX = 1e4;

struct Muchie {
    int sursa;
    int destinatie;
    int pondere;
};

struct Compare {
    bool operator()(const Muchie& a, const Muchie& b) {
        return a.pondere > b.pondere; // Ordinea inversă pentru min-heap
    }
};

int N, M, cost_total;
vector<vector<pair<int, int>>> lista_adiacenta(NMAX);
priority_queue<Muchie, vector<Muchie>, Compare> heap;
vector<bool> in_MST(NMAX, false);
vector<Muchie> MST;

void citire_graf(const char* fisier) {
    ifstream f(fisier);
    if (!f.is_open()) {
        cerr << "Eroare la deschiderea fisierului";
        return;
    }
    f >> N >> M;
    for (int i = 1; i <= M; i++) {
        int X, Y, C;
        f >> X >> Y >> C;
        lista_adiacenta[X - 1].push_back({C, Y - 1}); // Muchie de la nodul X-1 la nodul Y-1 cu ponderea C
        lista_adiacenta[Y - 1].push_back({C, X - 1}); // Muchie de la nodul Y-1 la nodul X-1 cu ponderea C
    }
    f.close();
}

void Prim_cu_heap() {
    heap.push({0, 0, 0}); // Adaugăm în coadă primul nod al grafului {sursa, destinatie, pondere}
    while (!heap.empty()) {
        auto edge = heap.top();
        heap.pop();
        int sursa = edge.sursa;
        int destinatie = edge.destinatie;
        int pondere = edge.pondere;

        if (in_MST[destinatie]) {
            continue;
        }

        in_MST[destinatie] = true;
        cost_total += pondere;
        if(sursa!=destinatie){
            Muchie temp;
            temp.sursa = sursa;
            temp.destinatie = destinatie;
            temp.pondere = pondere;
            MST.push_back(temp);
        }
        

        for (auto neighbor : lista_adiacenta[destinatie]) {
            if (!in_MST[neighbor.second]) {
                heap.push({destinatie, neighbor.second, neighbor.first});
            }
        }
    }
}

void afisare_lista_adiacenta() {
    for (int i = 0; i < N; i++) {
        cout << "Vecinii nodului " << i + 1 << ": ";
        for (const auto& vecin : lista_adiacenta[i]) {
            cout << "(COST: " << vecin.first << ", NOD_ADJ: " << vecin.second + 1 << ") ";
        }
        cout << endl;
    }
}

void afisare_lista_muchii(vector<Muchie>& lista) {
    for (auto uv : lista) {
        g << uv.sursa + 1 << " " << uv.destinatie + 1  << endl;
    }
}

int main() {
    citire_graf("apm.in");
    Prim_cu_heap();
    //afisare_lista_adiacenta();
    // Afisare MST
    g << cost_total << endl;
    g<<MST.size()<<endl;
    afisare_lista_muchii(MST);

    return 0;
}