#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e5;
struct X{
    int u, v, cst;
};

vector <X> muc;

bool cmp(X a, X b) {
    return a.cst < b.cst;
}

int r[NMAX + 5], sz[NMAX + 5];

int reprezentant(int node) {
    if (r[node] == node) return node;
    return r[node] = reprezentant(r[node]);
}

void uneste(int u, int v) {
    u = reprezentant(u), v = reprezentant(v);
    if (sz[u] > sz[v]) {
        r[v] = u;
        sz[u] += sz[v];
    }
    else {
        r[u] = v;
        sz[v] += sz[u];
    }
}

vector <pair<int, int>> sol;

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        muc.push_back({a, b, cost});
    }
    for (int i = 1; i <= n; i++) {
        sz[i] = 1, r[i] = i;
    }
    sort(muc.begin(), muc.end(), cmp);

    long long ans = 0;
    for (auto x: muc) {
        if (reprezentant(x.u) != reprezentant(x.v)) {
            uneste(x.u, x.v);
            ans += x.cst;
            sol.push_back({x.u, x.v});
        }
    }
    cout << ans << '\n' << sol.size() << '\n';
    for (auto x: sol) cout << x.first << " " << x.second << '\n';
    return 0;
}