#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

struct muchie {
    int nod1, nod2, cost;
    bool operator<(const muchie &other) const {
        return cost > other.cost;
    }
};

const int N = 1e5 + 5;
vector <int> root(N), depth(N);
vector <muchie> muchii;
priority_queue <muchie> muchii_date;

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

void unite(int node1, int node2) {
    node1 = find_root(node1);
    node2 = find_root(node2);
    if (depth[node2] < depth[node1])
        root[node2] = node1;
    else if (depth[node1] < depth[node2])
        root[node1] = node2;
    else {
        root[node1] = node2;
        depth[node2]++;
    }
}

int main() {
    int n, m, sum = 0;
    cin >> n >> m;
    depth.assign(n + 1, 1);
    for (int i = 1; i <= n; i++)
        root[i] = i;
    for (int i = 1; i <= m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        muchii_date.push({a, b, cost});
    }
    while (!muchii_date.empty() and muchii.size() < n) {
        muchie crt = muchii_date.top();
        muchii_date.pop();
        if (find_root(crt.nod1) != find_root(crt.nod2)) {
            unite(crt.nod1, crt.nod2);
            sum += crt.cost;
            muchii.push_back(crt);
        }
    }
    cout << sum << '\n' << muchii.size() << '\n';
    for (auto [nod1, nod2, _] : muchii)
        cout << nod1 << ' ' << nod2 << '\n';
    return 0;
}