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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int DIM = 200010;

struct edge {
    int node1, node2, cost;
};

int n, m, x, y, c;
int father[DIM];
edge edges[DIM];
vector<pair<int, int>> sol;

inline bool cmp(edge a, edge b) {
    return a.cost < b.cost;
}

int getRoot(int node) {
    while (father[node] > 0)
        node = father[node];
    return node;
}

void join(int root1, int root2) {
    if (father[root1] <= father[root2]) {
        father[root1] += father[root2];
        father[root2] = root1;
    } else {
        father[root2] += father[root1];
        father[root1] = root2;
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        edges[i] = {x, y, c };
    }

    sort(edges + 1, edges + m + 1, cmp);
    for (int i = 1; i <= n; i++)
        father[i] = -1;

    int minCost = 0;
    for (int i = 1; i <= m; i++) {
        int root1 = getRoot(edges[i].node1);
        int root2 = getRoot(edges[i].node2);
        if (root1 != root2) {
            minCost += edges[i].cost;
            sol.emplace_back(edges[i].node1, edges[i].node2);
            join(root1, root2);
        }
    }

    fout << minCost << '\n' << sol.size() << '\n';
    for (auto elem : sol)
        fout << elem.first << ' ' << elem.second << '\n';

    return 0;
}