#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

struct Edge {
    int left, right, cost;

    Edge(){}

    Edge(int left, int right, int cost) {
        this->left = left;
        this->right = right;
        this->cost = cost;
    }

    bool operator< (const Edge &other) {
        return this->cost < other.cost;
    }
};

int TT[200005];

int root(int nod) {
    if (TT[nod] == nod) return nod;
    TT[nod] = root(TT[nod]);
    return TT[nod];
}

void unite(const int &a, const int &b) {
    TT[b] = a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ifstream f("apm.in");
    ofstream g("apm.out");

    #define cin f
    #define cout g

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        TT[i] = i;

    vector<Edge> edges;

    for (int i = 1; i <= m; ++i) {
        int a, b, cost;
        cin >> a >> b >> cost;
        edges.push_back(Edge(a, b, cost));
    }

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

    vector<Edge> solution;

    int costTotal = 0;

    for (const auto &edge: edges) {
        int left = root(edge.left);
        int right = root(edge.right);

        if (left != right) {
            unite(left, right);
            costTotal += edge.cost;
            solution.push_back(Edge(edge.left, edge.right, 0    ));
        }
    }

    cout << costTotal << "\n";
    cout << solution.size() << "\n";

    for (const auto &edge: solution)
        cout << edge.left << " " << edge.right << "\n";

    return 0;
}