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

using namespace std;

class DisjointSet {
public:
    DisjointSet(int size) : parent_(size, -1) {
    }

    bool Unite(int a, int b) {
        auto root_a = Root(a);
        auto root_b = Root(b);
        if (root_a != root_b) {
            parent_[root_b] = root_a;
            return true;
        }
        return false;
    }

private:
    int Root(int node) {
        if (parent_[node] == -1) {
            return node;
        }
        return parent_[node] = Root(parent_[node]);
    }

    vector<int> parent_;
};

pair<int, vector<pair<int, int>>> FindMst(int nodes, vector<tuple<int, int, int>>& edges) {
    sort(edges.begin(), edges.end(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
        return get<2>(a) < get<2>(b);
    });

    vector<pair<int, int>> mst;
    int total = 0;

    DisjointSet dset(nodes);
    for (const auto& [a, b, cost] : edges) {
        if (dset.Unite(a, b)) {
            mst.push_back({a, b});
            total += cost;
        }
    }
    return {total, mst};
}

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

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

    vector<tuple<int, int, int>> graph(edges);
    for (auto& [a, b, cost] : graph) {
        fin >> a >> b >> cost;
        a -= 1;
        b -= 1;
    }

    auto [cost, mst] = FindMst(nodes, graph);
    fout << cost << "\n";
    fout << mst.size() << "\n";
    for (const auto& [a, b] : mst) {
        fout << a + 1 << " " << b + 1 << "\n";
    }
    return 0;
}