#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e5;
int parent[NMAX + 1], rank_[NMAX + 1];

struct Edge {
    int u, v, weight;
    bool operator<(const Edge &other) const {
        return weight < other.weight;
    }
};

vector<Edge> edges;

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (rank_[rootX] > rank_[rootY]) {
            parent[rootY] = rootX;
        } else if (rank_[rootX] < rank_[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank_[rootX]++;
        }
    }
}

vector<pair<int, int>> kruskal(int n, int m, ifstream &f) {
    for (int i = 1; i <= m; i++) {
        int x, y, c;
        f >> x >> y >> c;
        edges.push_back({x, y, c});
    }

    sort(edges.begin(), edges.end());
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        rank_[i] = 0;
    }

    vector<pair<int, int>> mst_edges;
    int apm = 0;
    for (const auto &edge : edges) {
        if (find(edge.u) != find(edge.v)) {
            unite(edge.u, edge.v);
            mst_edges.push_back({edge.u, edge.v});
            apm += edge.weight;
        }
    }
    return mst_edges;
}

int main() {
    int n, m;
    ifstream f("apm.in");
    ofstream g("apm.out");
    f >> n >> m;

    vector<pair<int, int>> mst_edges = kruskal(n, m, f);

    int apm = 0;
    for (const auto &edge : mst_edges) {
        for (const auto &e : edges) {
            if ((e.u == edge.first && e.v == edge.second) || (e.u == edge.second && e.v == edge.first)) {
                apm += e.weight;
                break;
            }
        }
    }

    g << apm << '\n';
    g << mst_edges.size() << '\n';
    for (const auto &e : mst_edges) {
        g << e.first << ' ' << e.second << '\n';
    }

    return 0;
}