#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()) {
        for (int i = 1; i <= n; i++) {
            int cmin = 1005, to = 0;
            for (const auto &[j, w] : g[i]) {
                if (w < cmin && root(i) != root(j)) {
                    cmin = w;
                    to = j;
                }
            }
            if (to) {
                join(i, to);
                ans += cmin;
                edges.push_back({i, to});
            }
        }
    }
    out << ans << '\n';
    out << (int) edges.size() << '\n';
    for (const auto &[u, v] : edges)
        out << u << ' ' << v << '\n';
    return 0;
}