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

using namespace std;

struct Edge
{
    int node_a, node_b;
    int cost;

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

using Graph = vector<Edge>;

int Father(vector<int> &fa, int node)
{
    if (fa[node] == -1) {
        return node;
    }
    return (fa[node] = Father(fa, fa[node]));
}

pair<int, vector<pair<int, int>>> GetMst(Graph &g, int nodes)
{
    sort(g.begin(), g.end());

    vector<int> fathers(nodes, -1);
    vector<pair<int, int>> edges;
    int cost = 0;

    for (const auto &edge : g) {
        auto fa = Father(fathers, edge.node_a);
        auto fb = Father(fathers, edge.node_b);
        if (fa == fb) {
            continue;
        }

        cost += edge.cost;
        fathers[fb] = fa;
        edges.push_back({edge.node_a, edge.node_b});
    }
    return {cost, edges};
}

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.node_a >> edge.node_b >> edge.cost;
        edge.node_a -= 1;
        edge.node_b -= 1;
    }

    auto mst_pair = GetMst(graph, nodes);
    fout << mst_pair.first << "\n" << nodes - 1 << "\n";

    for (const auto &edge : mst_pair.second) {
        fout << edge.first + 1 << " " << edge.second + 1 << "\n";
    }
    return 0;
}