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

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");


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

class DSU {
    int n;
    vector<int> par, siz;
public:
    DSU(int _n) : n(_n) {
        par.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            par[i] = i;
        }
        siz.assign(n + 1, 1);
    }
    int getRoot(int x) {
        return x == par[x] ? x : par[x] = getRoot(par[x]);
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y) {
            return false;
        }
        if (siz[x] >= siz[y]) {
            swap(x, y);
        }
        par[x] = y;
        siz[y] += siz[x];
        return true;
    }
};

vector<Edge> E, ans;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= M; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        E.push_back({ x, y, c });
    }

    sort(E.begin(), E.end());
    DSU dsu(N);

    long long cost_total = 0;
    for (auto e: E) {
        if (dsu.unite(e.x, e.y)) {
            ans.push_back(e);
            cost_total += e.c;
        }
    }
    
    cout << cost_total << '\n';
    cout << ans.size() << '\n';
    for (auto it : ans) {
        cout << it.x << ' ' << it.y << '\n';
    }

    return 0;
}