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

using namespace std;

struct Tree
{
    vector<pair<int, int>> edges;
    int cost;
};

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

template <typename T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;

Tree FindMst(const Graph &g)
{
    vector<int> pred(g.size(), -1);
    vector<bool> used(g.size(), false);

    vector<int> min_cost(g.size(), (1 << 30));
    min_cost[0] = 0;

    MinHeap<pair<int, int>> heap;
    heap.push({0, 0});

    Tree mst;
    mst.cost = 0;

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

        if (used[node]) {
            continue;
        } else if (pred[node] != -1) {
            mst.edges.push_back({pred[node], node});
            mst.cost += min_cost[node];
        }
        used[node] = true;

        for (const auto &e : g[node]) {
            auto next = e.first;
            auto cost = e.second;

            if (!used[next] && cost < min_cost[next]) {
                pred[next] = node;
                min_cost[next] = cost;
                heap.push({cost, next});
            }
        }
    }
    return 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 mst = FindMst(graph);
    fout << mst.cost << "\n";

    fout << mst.edges.size() << "\n";
    for (const auto &e : mst.edges) {
        fout << e.first + 1 << " " << e.second + 1 << "\n";
    }

    return 0;
}