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

using uint = int;
const uint NMAX = 200000 + 2;

uint parent[NMAX];
uint weight[NMAX];
uint n;

void init_dsu() {
    for(uint i = 0; i <= n; i++) {
        parent[i] = i;
        weight[i] = 1;
    }
}


uint root(uint i) {
    while(i != parent[i]) {
        //parent[i] = parent[parent[i]];
        i = parent[i];
    }
    return i;
}

bool fnd(uint a, uint b) {
    return (root(a) == root(b));
}

void unite(uint a, uint b) {
    const uint root_a = root(a);
    const uint root_b = root(b);

    if(weight[root_a] > weight[root_b]) {
        weight[root_a] += weight[root_b];
        parent[root_b] = root_a;
    } else {
        weight[root_b] += weight[root_a];
        parent[root_a] = root_b;
    }
}

int main() {
    ifstream in("apm.in");
    ofstream out("apm.out");
    in >> n;
    uint v;
    in >> v;
    init_dsu();

    vector<array<uint, 3>> graph_verts;
    graph_verts.resize(v);

    for(uint i = 0; i < v; i++) {
        in >> graph_verts[i][1] >> graph_verts[i][2];
        in >> graph_verts[i][0];
    }

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

    uint tree_cost = 0;
    vector<array<uint, 2>> tree_verts;

    for(const auto l : graph_verts) {
        const uint v1 = l[1];
        const uint v2 = l[2];
        if(fnd(v1, v2))
            continue;
        unite(v1, v2);
        tree_cost += l[0];
        tree_verts.push_back({v1, v2});
    }

    out << tree_cost << '\n' << tree_verts.size() << '\n';

    for(const auto l : tree_verts) {
        out << l[1] << ' ' << l[0] << '\n';
    }
}