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

using namespace std;

struct Edge
{
    int node1, node2;
    int cost;

    bool operator<(const Edge &other) const
    {
        return cost < other.cost;
    }
};

using Graph = vector<Edge>;

class Sets
{
public:
    Sets(int n) : fathers_(vector<int>(n, -1)) {}

    void Unite(int a, int b);

    bool SameGroup(int a, int b);

private:
    vector<int> fathers_;

    int get_root(int node);
};

void Sets::Unite(int a, int b)
{
    auto root_a = get_root(a);
    auto root_b = get_root(b);

    if (root_a != root_b) {
        fathers_[root_b] = root_a;
    }
}

bool Sets::SameGroup(int a, int b)
{
    return get_root(a) == get_root(b);
}

int Sets::get_root(int node)
{
    if (fathers_[node] == -1) {
        return node;
    }
    return fathers_[node] = get_root(fathers_[node]);
}

pair<int, vector<pair<int, int>>> FindMst(Graph &graph, int nodes)
{
    vector<pair<int, int>> mst;
    auto cost = 0;
    Sets sets(nodes);

    sort(graph.begin(), graph.end());
    for (const auto &edge : graph) {
        auto x = edge.node1;
        auto y = edge.node2;
        if (sets.SameGroup(x, y)) {
            continue;
        }

        cost += edge.cost;
        sets.Unite(x, y);
        mst.push_back({x, y});
    }

    return {cost, mst};
}

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

    int nodes, edges;
    fin >> nodes >> edges;

    Graph graph(edges);
    for (auto &edge : graph) {
        fin >> edge.node1 >> edge.node2 >> edge.cost;
        edge.node1 -= 1;
        edge.node2 -= 1;
    }

    auto res = FindMst(graph, nodes);
    fout << res.first << "\n";

    fout << nodes - 1 << "\n";
    for (const auto &edge : res.second) {
        fout << edge.first + 1 << " " << edge.second + 1 << "\n";
    }

    return 0;
}