#include <bits/stdc++.h>
using namespace std;

int ancestor[200005];
int n, m;

struct edge {
    int u, v, cost;

    edge(int u, int v, int cost) {
        this->u = u;
        this->v = v;
        this->cost = cost;
    }

    static bool comp(edge a, edge b) {
        return a.cost < b.cost;
    }
};

int update(int currNode) {
    if (ancestor[currNode] == currNode) {
        return currNode;
    }

    ancestor[currNode] = update(ancestor[currNode]);
    return ancestor[currNode];
}


int main() {
    cin >> n >> m;

    vector <edge> edges;
    for (int i = 0; i < m; ++i) {
        int u, v, cost;

        cin >> u >> v >> cost;

        edges.push_back(edge(u, v, cost));
    }

    for (int i = 1; i <= n; ++i) {
        ancestor[i] = i;
    }

    sort(edges.begin(), edges.end(), edge::comp);

    vector <edge> result;
    int cost = 0;
    for (edge curr : edges) {
        update(curr.u);
        update(curr.v);

        if (ancestor[curr.u] != ancestor[curr.v]) {
            ancestor[ancestor[curr.u]] = ancestor[ancestor[curr.v]];
            result.push_back(curr);
            cost += curr.cost;
        }
    }

    cout << cost << '\n';
    cout << result.size() << '\n';
    for (edge curr : result) {
        cout << curr.u << ' ' << curr.v << '\n';
    }

    return 0;
}