#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>


class WQUPC
{
public:
    WQUPC(int n)
        : id(new int[n])
        , size(new int[n])
    {
        for (int i = 0; i < n; ++i) {
            id[i] = i;
            size[i] = 1;
        }
    }

    ~WQUPC()
    {
        delete id;
        delete size;
    }

    bool areConnected(int p, int q)
    {
        return root(p) == root(q);
    }

    void connect(int p, int q)
    {
        int rootP = root(p);
        int rootQ = root(q);

        // Apply weighting.
        if (size[rootP] < size[rootQ]) {
            id[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            id[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
    }

private:
    int root(int i)
    {
        // Apply path compression.
        if (i != id[i])
            id[i] = root(id[i]);

        return id[i];
    }

    int *id;
    int *size;
};

struct Edge {

    Edge(int _x, int _y, int _w)
        : x(_x)
        , y(_y)
        , w(_w)
    {}

    int x;
    int y;
    int w;
};

struct weight_cmp {

    bool operator()(const Edge &lhs, const Edge &rhs) const
    {
        return lhs.w < rhs.w;
    }
};


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

    int N, M;
    fin >> N >> M;

    std::vector<Edge> edges;
    for (auto i = 0; i < M; ++i) {
        int x, y, w;
        fin >> x >> y >> w;

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

    auto weight_cmp = [](const Edge &lhs, const Edge &rhs) -> bool {
        return lhs.w < rhs.w;
    };
    std::sort(edges.begin(), edges.end(), weight_cmp);


    auto weight = 0;
    std::vector<Edge> apm_edges;

    WQUPC uf(N);
    for (auto &edge : edges)
        if (!uf.areConnected(edge.x, edge.y)) {
            weight += edge.w;
            apm_edges.emplace_back(edge);
            uf.connect(edge.x, edge.y);
        }

    fout << weight << '\n';
    fout << apm_edges.size() << '\n';
    for (auto &edge : apm_edges)
        fout << edge.y << ' ' << edge.x << '\n';

    return 0;
}