#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 component[NMAX + 5];

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++) {
        component[i] = i;
    }

    vector<pair<int, int>>edges;

    auto check = [&] () {
        for (int i = 1; i < n; i++) {
            if (component[i] != component[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 && component[i] != component[j]) {
                    cmin = w;
                    to = j;
                }
            }
            if (to) {
                component[i] = component[to] = min(component[i], component[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;
}