#include <bits/stdc++.h>

constexpr size_t MAXNODE = 200000;

struct trip {
    int price, from, to;
    trip() = default;
    trip(int a, int b, int c):
        price(a), from(b), to(c) {}
    bool operator< (trip o) const {
        return price < o.price;
    }
};

std::vector<trip> edges;


std::array<int, MAXNODE> jumpback;

int
root (int node) {
    if (jumpback[node] != node)
        jumpback[node] = root(jumpback[node]);
    return jumpback[node];
}

void
unite (int a, int b) {
    int ra = root(a), rb = root(b);
    jumpback[rb] = ra;
}


int
find_apm (int nodes, std::vector<std::pair<int, int>> &ret_edges) {
    std::sort(edges.begin(), edges.end());
    for (int i = 0; i < nodes; ++ i)
        jumpback[i] = i;


    auto it = edges.begin();
    int ret = 0;
    ret_edges.resize(0);
    ret_edges.reserve(nodes - 1);

    for (int i = 1; i < nodes;) {
        auto [price, from, to] = *(it ++);
        if (root(from) != root(to)) {
            ret += price;
            ret_edges.emplace_back(from + 1, to + 1);
            unite(from, to);
            ++ i;
        }
    }
    return ret;
}

int main () {
    int n, m;
    std::ifstream f("apm.in");
    std::ofstream g("apm.out");

    f >> n >> m;
    edges.reserve(m);

    for (int i = 0; i != m; ++ i) {
        int from, to, price;
        f >> from >> to >> price;
        -- from, -- to;
        edges.emplace_back(price, from, to);
    }

    std::vector<std::pair<int, int>> apm_edges;
    g << find_apm(n, apm_edges) << '\n';
    g << apm_edges.size() << '\n';
    for (auto [a, b]: apm_edges)
        g << a << ' ' << b << '\n';
}