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

using namespace std;

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

const int NODE_DIM = 200010;
const int EDGE_DIM = 400010;

struct Edge {
    int n1, n2, c;
};

int n, m, x, y, c;
int father[NODE_DIM];
Edge edges[EDGE_DIM], sol[EDGE_DIM];

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, [](Edge a, Edge b) { return a.c < b.c; });
    for (int i = 1; i <= n; i++)
        father[i] = -1;

    int minCost = 0, solCnt = 0;
    for (int i = 1; i <= m; i++) {
        int root1 = getRoot(edges[i].n1);
        int root2 = getRoot(edges[i].n2);
        if (root1 != root2) {
            minCost += edges[i].c;
            sol[++solCnt] = edges[i];
            join(root1, root2);
        }
    }

    fout << minCost << '\n' << solCnt << '\n';
    for (int i = 1; i <= solCnt; i++)
        fout << sol[i].n1 << ' ' << sol[i].n2 << '\n';

    return 0;
}