#include <algorithm>
#include <array>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <vector>
constexpr int g_maxn = 200'001;
class edge {
   private:
    int m_a = 0;
    int m_b = 0;
    int m_cost = 0;
    using ref = edge &;
   public:
    edge() noexcept = default;
    edge(edge const &) noexcept = default;
    edge(edge &&) noexcept = default;
    ~edge() noexcept = default;
    edge(int const a, int const b, int const cost)
        : m_a{a}, m_b{b}, m_cost{cost} {}
    auto operator=(edge const &) noexcept -> ref = default;
    auto operator=(edge &&) noexcept -> ref = default;
    auto first() const noexcept -> int { return m_a; }
    auto second() const noexcept -> int { return m_b; }
    auto cost() const noexcept -> int { return m_cost; }
};
std::vector<edge> g_edges;
std::vector<edge> g_answer;
std::array<int, g_maxn> g_groups;
auto get_group(int const i) noexcept -> int {
    if (g_groups[i] == i) {
        return i;
    }
    g_groups[i] = get_group(g_groups[i]);
    return g_groups[i];
}
auto unite(int const i, int const j) noexcept -> void {
    g_groups[get_group(i)] = get_group(j);
}
auto main(int, char *[]) noexcept -> int {
    std::ifstream f{"apm.in"};
    std::ofstream g{"apm.out"};
    int n = 0;
    int m = 0;
    f >> n >> m;
    g_edges.reserve(m);
    g_answer.reserve(m);
    for (int i = 0; i < m; ++i) {
        int a = 0;
        int b = 0;
        int cost = 0;
        f >> a >> b >> cost;
        g_edges.emplace_back(a, b, cost);
        g_groups[i] = i;
    }
    std::sort(g_edges.begin(), g_edges.end(),
              [](edge const &a, edge const &b) { return a.cost() < b.cost(); });
    std::int64_t total_cost = 0;
    for (auto const &e : g_edges) {
        if (get_group(e.first()) != get_group(e.second())) {
            total_cost += e.cost();
            unite(e.first(), e.second());
            g_answer.push_back(e);
        }
    }
    g << total_cost << std::endl;
    g << g_answer.size() << std::endl;
    for (auto const &e : g_answer) {
        g << e.first() << ' ' << e.second() << std::endl;
    }
}