#include <bits/stdc++.h>

using namespace std;

struct edge {
    int a, b, w;
    auto operator<(const edge& other) const {
        w < other.w;
    }
};

istream& operator>>(istream& in, edge& e) {
    return in >> e.a >> e.b >> e.w;
}

struct DSU {
    vector<int> parent, size;
    DSU(int n) : parent(n+1), size(n+1, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        return x == parent[x] ? x : parent[x] = find(parent[x]);
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        if (size[x] < size[y])
            swap(x, y);
        parent[y] = x;
        size[x] += size[y];
        return true;
    }
};

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

    int n, m;
    cin >> n >> m;
    vector<edge> edges(m);
    for (auto& e : edges)
        cin >> e;

    sort(edges.begin(), edges.end(), [](const edge& a, const edge& b) {
        return a.w < b.w;
    });
    DSU dsu(n);
    vector<edge> mst;
    for (const auto& e : edges) {
        if (dsu.unite(e.a, e.b))
            mst.push_back(e);
    }

    int mst_cost = accumulate(mst.begin(), mst.end(), 0, [](int acc, const edge& e) {
        return acc + e.w;
    });

    cout << mst_cost << '\n';
    cout << mst.size() << '\n';
    for (const auto& e : mst)
        cout << e.a << ' ' << e.b << '\n';

}