#include <algorithm>
#include <array>
#include <cstdint>
#include <fstream>
#include <numeric>
#include <tuple>
#include <vector>


/* Defines */
using u32 = uint32_t;
using i32 = int32_t;

using weightedEdgeT = std::tuple<size_t, size_t, i32>;
using edgeT = std::tuple<size_t, size_t>;

template<typename T>
class DisjointForest {
public:
    DisjointForest (const T &nodes): m_jumpback(nodes) {
        std::iota(m_jumpback.begin(), m_jumpback.end(), 0);
    }

    const T& component (const T &node) { return root(node); }

    bool areInSameComponent (const T &lhs, const T &rhs) {
        return component(lhs) == component(rhs);
    }

    void addEdge (const T &from, const T &to) {
        m_jumpback[root(from)] = root(to);
    }
private:
    const T& root (const T &node) {
        if (node != m_jumpback[node])
            m_jumpback[node] = root(m_jumpback[node]);
        return m_jumpback[node];
    }

    std::vector<T> m_jumpback;
};

constexpr const char *inputFilename = "apm.in";
constexpr const char *outputFilename = "apm.out";


/* Function definitions */
void readInput();
void writeAnswer(i32 minimum_cost, const std::vector<edgeT> &treeEdges);

bool ascendingCost(const weightedEdgeT &lhs, const weightedEdgeT &rhs);


/* Global variables */
size_t nodes;
std::vector<weightedEdgeT> edges;


/* Functoin declarations */
void readInput () {
    std::ifstream file(inputFilename);
    file.exceptions(file.badbit | file.eofbit | file.failbit);

    size_t edgeCount;
    file >> nodes >> edgeCount;

    edges.reserve(edgeCount);

    for (size_t i = 0; i != edgeCount; ++ i) {
        size_t u, v;
        i32 cost;
        file >> u >> v >> cost;
        -- u, -- v;

        edges.emplace_back(u, v, cost);
    }
}

void writeAnswer (i32 minimum_cost, const std::vector<edgeT> &treeEdges) {
    std::ofstream file(outputFilename);
    file.exceptions(file.badbit | file.eofbit | file.failbit);

    file << minimum_cost;
    file.put('\n');

    file << treeEdges.size();
    file.put('\n');

    for (auto [left, right]: treeEdges)
        file << left + 1 << ' ' << right + 1 << '\n';
}

bool ascendingCost (const weightedEdgeT &lhs, const weightedEdgeT &rhs) {
    return std::get<2>(lhs) < std::get<2>(rhs);
}


int main () {
    readInput();
    std::sort(edges.begin(), edges.end(), ascendingCost);


    DisjointForest<size_t> forest(nodes);

    size_t totalCost = 0;
    std::vector<edgeT> tree; tree.reserve(nodes - 1);

    auto addEdge = [&forest, &totalCost, &tree] (size_t left, size_t right, i32 cost) {
        totalCost += cost;
        forest.addEdge(left, right);
        tree.emplace_back(left, right);
    };


    for (auto [u, v, cost]: edges) {
        if (!forest.areInSameComponent(u, v))
            addEdge(u, v, cost);
    }


    writeAnswer(totalCost, tree);
}