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

using namespace std;

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

struct edge {
    int a, b, val;
};

bool cmp(const edge& a, const edge& b) {
    return a.val < b.val;
}

vector<edge> edges;
vector<edge> ans;
int tata[200100];

int super_tata(int node) {
    if (tata[node] != node) {
        tata[node] = super_tata(tata[node]);
    }
    return tata[node];
}

void unire(int a, int b) {
    int ta = super_tata(a);
    int tb = super_tata(b);
    tata[tb] = ta;
}

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

    int nodes, nr_edges;
    cin >> nodes >> nr_edges;

    edges.resize(nr_edges);
    for (int i = 0; i < nr_edges; i++) {
        cin >> edges[i].a >> edges[i].b >> edges[i].val;
    }

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

    for (int i = 1; i <= nodes; i++) {
        tata[i] = i;
    }

    long long cont = 0;

    for (int i = 0; i < nr_edges; i++) {
        int a = edges[i].a;
        int b = edges[i].b;
        if (super_tata(a) != super_tata(b)) {
            cont += edges[i].val;
            ans.push_back(edges[i]);
            unire(a, b);
        }
    }

    cout << cont << '\n';
    cout << ans.size() << '\n';
    for (const auto& x : ans) {
        cout << x.a << " " << x.b << '\n';
    }

    return 0;
}