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

using namespace std;

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

struct Edge {
    int x, y, cost;
    bool operator<(const Edge& other) const {
        return cost < other.cost;
    }
};

int N, M;
vector<Edge> edges;
vector<vector<int>> setContent;
vector<int> label;

void joinSets(int x, int y) {
    if (setContent[x].size() < setContent[y].size()) {
        swap(x, y);
    }
    for (int elem : setContent[y]) {
        setContent[x].push_back(elem);
        label[elem] = x;
    }
}

int main() {
    fin >> N >> M;
    edges.resize(M);
    for (auto& edge : edges) {
        fin >> edge.x >> edge.y >> edge.cost;
    }
    sort(edges.begin(), edges.end());

    setContent.resize(N + 1);
    label.resize(N + 1);
    for (int i = 1; i <= N; ++i) {
        label[i] = i;
        setContent[i].assign(1, i);
    }
    int totalCost = 0;
    vector<pair<int, int>> treeEdges;
    for (const auto& edge : edges) {
        if (label[edge.x] != label[edge.y]) {
            joinSets(label[edge.x], label[edge.y]);
            totalCost += edge.cost;
            treeEdges.emplace_back(edge.x, edge.y);
        }
    }
    fout << totalCost << "\n" << treeEdges.size() << "\n";
    for (const auto& edge : treeEdges) {
        fout << edge.first << " " << edge.second << "\n";
    }
    return 0;
}