#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

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

vector<int> parent, rnk;

void make_set(int v) {
    parent[v] = v;
    rnk[v] = 0;
}

int find_set(int v) {
    if (parent[v] == v)
        return v;
    parent[v] = find_set(parent[v]);
    return parent[v];
}

void union_set(int v, int u) {
    v = find_set(v);
    u = find_set(u);

    if (u != v) {
        if (rnk[u] < rnk[v])
            swap(u, v);

        parent[v] = u;
        if (rnk[u] == rnk[v])
            rnk[u]++;
    }
}

// it useful to define an Edge
struct Edge
{
    int u, v, w;
    bool operator< (Edge const& other) {
        return w < other.w;
    }
};

int main(int argc, char const *argv[])
{
    int n, m;
    cin >> n >> m;
    vector<Edge> edges;
    parent.assign(n + 1, 0);
    rnk.assign(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    for (int i = 1; i <= n; i++) {
        make_set(i);
    }

    sort(edges.begin(), edges.end());

    int selected = 0, sum = 0, idx = 0;
    vector<pair<int, int>> selected_ed;

    for (const auto& edge : edges) {
        if (find_set(edge.u) != find_set(edge.v)) {
            union_set(edge.u, edge.v);
            selected++;
            sum += edge.w;
            selected_ed.push_back({edge.u, edge.v});
        }
        if (selected == n-1) break;
    }

    cout << sum << "\n" << selected << "\n";
    for (auto ed : selected_ed)
        cout << ed.first << " " << ed.second << "\n";
    return 0;
}