#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

const int NMAX = 2e5;

vector<pair<int, int>>g[NMAX + 5];
int p[NMAX + 5];

int root (int u) {
    return (u == p[u]? u : p[u] = root(p[u]));
}
void join (int u, int v) {
    u = root(u), v = root(v);
    p[u] = v;
}

int main() {
    int n, m;
    in >> n >> m;
    while (m--) {
        int u, v, w;
        in >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i++) {
        p[i] = i;
    }

    vector<pair<int, int>>edges;

    auto check = [&] () {
        for (int i = 1; i < n; i++) {
            if (root(i) != root(i + 1))
                return false;
        }
        return true;
    };

    int ans = 0;
    while (!check()) {
        int cmin[n + 1];
        for (int i = 1; i <= n; i ++) {
            cmin[i] = 1005;
        }
        int from[n + 1], to[n + 1];
        for (int i = 1; i <= n; i++) {
            int component = root(i);
            for (const auto &[j, w] : g[i]) {
                if (w < cmin[component] && component != root(j)) {
                    cmin[component] = w;
                    from[component] = i;
                    to[component] = j;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            if (cmin[i] != 1005 && root(i) != root(to[i])) {
                ans += cmin[i];
                join(from[i], to[i]);
                edges.push_back({from[i], to[i]});
            }
        }
    }
    out << ans << '\n';
    out << (int) edges.size() << '\n';
    for (const auto &[u, v] : edges)
        out << u << ' ' << v << '\n';
    return 0;
}