// O(mlogn) - min heap

#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>

using namespace std;

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

// Custom comparator to compare vectors based on their first element
struct VectorComparator {
    bool operator()(const vector<int>& v1, const vector<int>& v2) const {
        return v1[0] > v2[0]; // Change to v1[0] < v2[0] for min-heap
    }
};

void prim (vector<vector<pair<int,int>>> adjacencyList, int n) {
    
    // vector<int> : tipul elementelor pe care queue-ul le va stoca
    // vector<vector<int>> : heap-ul foloseste un vector pentru a stoca tupluri de 3
    // VectorComparator : comparator custom folosit pentru a determina
    //      ordinea elementelor din queue; v1[0] > v2[0] => min heap
    //      deci in varful heap-ului va fi cel mai mic element
    // sortarea se va face dupa primul element din pereche
    priority_queue<vector<int>, vector<vector<int>>, VectorComparator> priorityQueue;

    // Initializare vectorul cu noduri deja prezente in MST
    vector<bool> verticesInMST(n + 1, false);

    // Initializare rezultat
    vector<vector<int>> resulted_mst;

    // Numar total cost
    int total_cost = 0;
    // Numar total muchii
    int no_edges = 0;

    int startWeight = 0; // va fi 0 la inceput
    int startSource = 1; // incep cu nodul 1
    int startDestination = 0; // nu este relevant acum

    // Adaug nodul de start in heap, cu prioritatea 0, deci va fi in varf
    priorityQueue.push({startWeight, startSource, startDestination});

    // Cat timp exista noduri in heap
    while (!priorityQueue.empty()) {
        // Obtin nodul curent
        vector<int> currentElement = priorityQueue.top();
        // Obtin cost, nod sursa, nod destinatie din heap
        int currentWeight = currentElement[0];
        int sourceVertex = currentElement[1];
        int destinationVertex = currentElement[2];
        // Elimin nodul
        priorityQueue.pop();

        // Daca am vizitat deja nodul curent, trecem la urmatorul
        // element din heap
        if (verticesInMST[sourceVertex]) {
            continue;
        }

        // Marchez nodul ca vizitat
        verticesInMST[sourceVertex] = true;

        if (currentWeight != 0) {
            resulted_mst.push_back({sourceVertex, destinationVertex, currentWeight});
            // Actualizez numarul de muchii
            no_edges += 1;
        }

        // Actualizez costul
        total_cost += currentWeight;

        for (const auto& edge : adjacencyList[sourceVertex]) {
            int destination = edge.first;
            int weight = edge.second;

            // Verificam daca nodurile adiacente nodului sursa 
            // au fost sau nu vizitate; daca nu, adaugam in heap
            // aceste noduri, impreuna cu costul lor
            if (!verticesInMST[destination]) {
                priorityQueue.push({weight, destination, sourceVertex});
            }
        }
    }

    fout << total_cost << endl;
    fout << no_edges << endl;

    for (const auto& edge : resulted_mst) {
        fout << edge[0] << " " <<  edge[1] << endl;
    }
}

int main() {
    int N, M;
    fin >> N >> M;

    vector<vector<pair<int,int>>> adjacencyList(N + 1);

    for (int i = 0; i < M; i++) {
        int X, Y, C;
        fin >> X >> Y >> C;
        adjacencyList[X].emplace_back(Y, C);
        adjacencyList[Y].emplace_back(X, C);
        
    }
    prim(adjacencyList, N);

    return 0;
}

// Varianta 1 - daca folosim vector de reprezentanti
// Sortare -> O(mlogm) = O(mlogn)
// n * Initializare -> O(n)
// 2m * Reprezentare -> O(m)
// (n - 1) * Reuneste -> O(n^2)
// Total -> O(mlogn + n^2)

// Varianta 2 - daca folosim arbori Union / Find
// Sortare -> O(mlogm) = O(mlogn)
// n * Initializare -> O(n)
// 2m * Reprezentare -> O(mlogn)
// (n - 1) * Reuneste -> O(nlogn)
// Total -> O(mlogn)

// DESCRIERE VARIANTA 2
// memoram componentele conexe ca arbori, folosind vectorul tata
// reprezentantul componentei va fi radacina arborelui
// reuniunea a doi arbori => radacina unui arbore devine fiu al radacinii celuilalt arbore
// reuniunea se va face  in functie de inaltimea/dimensiunea arborilor
// (reuniune ponderata), pentru a obtine arbori de inaltime mica => arbori de inaltime logaritmica
// arborele cu inaltimea mai mica devine subarbore al radacinii celuilalt arbore