// https://www.infoarena.ro/problema/apm - Szücs Patrik - Kevin
#include <fstream>
#include <vector>
#include <algorithm>

#define vint std::vector<int>

struct edge
{
    int x, y, cost;

    bool operator<(const edge &a) const
    {
        return cost < a.cost;
    }
};

int find(int x, vint &parent)
{
    if (parent[x] != x)
        parent[x] = find(parent[x], parent);

    return parent[x];
}

int main()
{
    int n, m;

    std::ifstream in("apm.in");
    in >> n >> m;

    std::vector<edge> edges;
    edges.reserve(m);
    while (m--)
    {
        int x, y, c;
        in >> x >> y >> c;

        edges.push_back({x, y, c});
    }
    in.close();

    sort(edges.begin(), edges.end());

    vint parent(n + 1), size(n + 1, 1);
    for (int i = 1; i <= n; i++)
        parent[i] = i;

    std::vector<std::pair<int, int>> ans;
    int s = 0;

    for (edge &i : edges)
    {
        if ((int)ans.size() == n - 1)
            break;

        int px = find(i.x, parent), py = find(i.y, parent);

        if (px != py)
        {
            if (size[px] < size[py])
                std::swap(px, py);

            parent[py] = px;
            size[px] += size[py];
            s += i.cost;
            ans.push_back({i.x, i.y});
        }
    }

    std::ofstream out("apm.out");
    out << s << '\n'
        << ans.size();
    for (auto &i : ans)
        out << '\n'
            << i.first << ' ' << i.second;

    return 0;
}