#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

void kruskal(int n, int m, priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>>& edges) {
    vector<int> repr(n + 1);
    for (int i = 1; i <= n; ++i) {
        repr[i] = i;
    }

    int total_cost = 0;
    int edges_used = 0;
    vector<pair<int, int>> mst_edges;

    while (!edges.empty() && edges_used < n - 1) {
        auto [weight, u, v] = edges.top();
        edges.pop();

        int repr_u = repr[u];
        int repr_v = repr[v];

        if (repr_u != repr_v) {
            total_cost += weight;
            mst_edges.push_back({v, u});
            ++edges_used;

            for (int i = 1; i <= n; ++i) {
                if (repr[i] == repr_v) {
                    repr[i] = repr_u;
                }
            }
        }
    }

    fout << total_cost << '\n' << n - 1 << '\n';
    for (const auto& edge : mst_edges) {
        fout << edge.first << ' ' << edge.second << '\n';
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> edges;

    for (int i = 0; i < m; ++i) {
        int u, v, weight;
        fin >> u >> v >> weight;
        edges.push({weight, u, v});
    }

    kruskal(n, m, edges);

    return 0;
}