#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int NMAX = 200505;

struct edge {
    int from, to, cost;

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

int N, M;
vector<edge> allEdges;
int parent[NMAX], size[NMAX];

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});
    }
}

int findSet(int node) {
    if (parent[node] == node) {
        return node;
    }

    return parent[node] = findSet(parent[node]);
}

void merge(int firstNode, int secondNode) {
    int firstComponent = findSet(firstNode);
    int secondComponent = findSet(secondNode);
    if (firstComponent == secondComponent) {
        return;
    }

    if (size[firstComponent] < size[secondComponent]) {
        parent[firstComponent] = secondComponent;
        size[firstComponent] += size[secondComponent];
    } else {
        parent[secondComponent] = firstComponent;
        size[secondComponent] += size[firstComponent];
    }
}

void solve() {
    sort(allEdges.begin(), allEdges.end());

    for (int i = 1; i <= N; i++) {
        parent[i] = i;
        size[i] = 1;
    }

    int result = 0;
    vector<edge> sol;
    for (edge& candidate : allEdges) {
        if (findSet(candidate.from) != findSet(candidate.to)) {
            result += candidate.cost;
            sol.push_back(candidate);
            
            merge(candidate.from, candidate.to);
        }
    }

    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;
}