#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct edge {
    int from, to, cost;

    bool operator < (const edge& other) const {
        return cost < other.cost;
    }
};

int N, M;
vector<edge> allEdges;

void read() {
    scanf("%d%d", &N, &M);
    int x, y, cost;
    for (int edgeIdx = 0; edgeIdx < M; edgeIdx++) {
        scanf("%d%d%d", &x, &y, &cost);
        allEdges.push_back({x, y, cost});
    }
}

void solve() {
    sort(allEdges.begin(), allEdges.end());
    vector<vector<int>> components(N + 1);
    vector<int> whatComponent(N + 1);

    for (int i = 1; i <= N; i++) {
        whatComponent[i] = i - 1;
        components[i - 1].push_back(i);
    }

    int result = 0;
    vector<edge> sol;
    for (edge& candidate : allEdges) {
        if (whatComponent[candidate.from] != whatComponent[candidate.to]) {
            result += candidate.cost;
            sol.push_back(candidate);

            int smallerComponent, largerComponent;
            if (components[whatComponent[candidate.from]].size() < components[whatComponent[candidate.to]].size()) {
                smallerComponent = whatComponent[candidate.from];
                largerComponent = whatComponent[candidate.to];
            } else {
                smallerComponent = whatComponent[candidate.to];
                largerComponent = whatComponent[candidate.from];
            }

            for (auto& node : components[smallerComponent]) {
                whatComponent[node] = largerComponent;
                components[largerComponent].push_back(node);
            }
            components[smallerComponent].clear();
        }
    }

    printf("%d\n", result);
    printf("%d\n", (int) sol.size());
    for (edge& usedEdge : sol) {
        printf("%d %d\n", usedEdge.from, usedEdge.to);
    }
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    read();
    solve();
    return 0;
}