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


using i32 = int32_t;
using u32 = uint32_t;

constexpr size_t MAX_NODES = 200000;


std::vector<std::tuple<size_t, size_t, i32>> edges;

std::array<size_t, MAX_NODES> jumpback;

size_t root (size_t node) {
    if (jumpback[node] != node)
        jumpback[node] = root(jumpback[node]);

    return jumpback[node];
}

void combine (size_t a, size_t b) {
    jumpback[root(a)] = root(b);
}

bool inTheSameComponent (size_t a, size_t b) {
    return root(a) == root(b);
}


int main () {
    std::ifstream in("apm.in");
    std::ofstream out("apm.out");

    size_t nodeCount, edgeCount;
    in >> nodeCount >> edgeCount;

    edges.reserve(edgeCount);

    for (size_t i = 0; i != edgeCount; ++ i) {
        size_t x, y;
        i32 cost;
        in >> x >> y >> cost;
        -- x, -- y;

        edges.emplace_back(x, y, cost);
    }

    std::sort(edges.begin(), edges.end(), [](auto a, auto b){ return std::get<2>(a) < std::get<2>(b);});

    for (size_t i = 0; i != nodeCount; ++ i)
        jumpback[i] = i;


    i32 totalCost = 0;
    std::vector<std::pair<size_t, size_t>> tree;
    auto addEdge = [&totalCost, &tree] (size_t u, size_t v, i32 w) {
        totalCost += w; tree.emplace_back(u, v);
        combine(u, v);
    };

    tree.reserve(nodeCount - 1);
    for (auto [u, v, w]: edges)
        if (!inTheSameComponent(u, v))
            addEdge(u, v, w);

    out << totalCost << '\n';

    out << tree.size() << '\n';

    for (auto [u, v]: tree)
        out << u + 1 << ' ' << v + 1 << '\n';
}