#include <fstream>
#include <queue>
#include <vector>

using namespace std;

using Graph = vector<vector<pair<int, int>>>;

struct Edge
{
    int node1, node2;
    int cost;
};

struct CmpEdges
{
    bool operator()(const Edge &a, const Edge &b)
    {
        return a.cost > b.cost;
    }
};

using Heap = priority_queue<Edge, vector<Edge>, CmpEdges>;

pair<int, vector<pair<int, int>>> FindMst(const Graph &g)
{
    vector<bool> used(g.size(), false);
    vector<pair<int, int>> mst;
    auto cost = 0;

    Heap heap;
    heap.push({.node1 = -1, .node2 = 0, .cost = 0});

    while (!heap.empty()) {
        auto edge = heap.top();
        heap.pop();

        if (used[edge.node2]) {
            continue;
        }

        used[edge.node2] = true;
        if (edge.node1 != -1) {
            mst.push_back({edge.node1, edge.node2});
            cost += edge.cost;
        }

        for (const auto &next : g[edge.node2]) {
            if (!used[next.first]) {
                heap.push({
                    .node1 = edge.node2,
                    .node2 = next.first,
                    .cost = next.second
                });
            }
        }
    }
    return {cost, mst};
}

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

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

    Graph graph(nodes);
    for (int i = 0; i < edges; i += 1) {
        int a, b, cost;
        fin >> a >> b >> cost;
        graph[a - 1].push_back({b - 1, cost});
        graph[b - 1].push_back({a - 1, cost});
    }

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

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

    return 0;
}