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

struct DSU {
    std::vector<int> parent;
    std::vector<int> height;

    DSU(int n) {
        parent.resize(n);
        height.resize(n);

        for (int i = 0; i < n; i += 1) {
            parent[i] = i, height[i] = 1;
        }
    }

    int Find(int x) {
        int root = x;
        while (root != parent[root]) {
            root = parent[root];
        }

        int elem = x;
        while (elem != root) {
            int temp = parent[elem];
            parent[elem] = root;
            elem = temp;
        }
        return root;
    }

    void Union(int x, int y) {
        x = Find(x), y = Find(y);

        if (height[x] < height[y]) {
            parent[x] = y;
        } else {
            parent[y] = x;
            if (height[x] == height[y]) {
                height[x] += 1;
            }
        }
    }

    ~DSU() {
        parent.clear();
        height.clear();
    }
};

struct Edge {
    int node1, node2, cost;

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

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

    int n, m; fin >> n >> m;
    std::vector<Edge> edges(m);
    for (int i = 0; i < m; i += 1) {
        int u, v, cost; fin >> u >> v >> cost; u -= 1, v -= 1;
        edges[i] = Edge{u, v, cost};
    }

    std::sort(edges.begin(), edges.end());

    DSU dsu(n);

    int totalCost = 0;
    std::vector<Edge> solEdges;
    for (int i = 0; i < m; i += 1) {
        if (dsu.Find(edges[i].node1) != dsu.Find(edges[i].node2)) {
            totalCost += edges[i].cost;
            solEdges.emplace_back(edges[i]);
            dsu.Union(edges[i].node1, edges[i].node2);
        }
    }

    fout << totalCost << '\n' << solEdges.size() << '\n';
    for (auto& edge : solEdges) {
        fout << edge.node1 + 1 << ' ' << edge.node2 + 1 << '\n';
    }

    edges.clear(), solEdges.clear();
    fin.close(), fout.close();
    return 0;
}