#include <iostream>
#include <fstream>
#include <stdint.h>
#include <algorithm>

const int32_t MAX_N = 200000;
const int32_t MAX_M = 400000;

struct Edge {
    int32_t x, y, c;
};

int32_t parent[MAX_N];
int32_t depth[MAX_N];
bool used[MAX_N];

Edge edges[MAX_M];
bool edgeUsed[MAX_M];

int32_t Root(int32_t node) {
    for(; parent[node] != -1; node = parent[node]);
    return node;
}
void Merge(int32_t root1, int32_t root2) {
    if(depth[root1] > depth[root2]) {
        parent[root2] = root1;
    } else if(depth[root1] < depth[root2]) {
        parent[root1] = root2;
    } else {
        parent[root2] = root1;
        ++depth[root1];
    }
}
bool Compare(const Edge& edge1, const Edge& edge2) {
    return edge1.c < edge2.c;
}

int main() {
    std::ifstream fin("apm.in");
    std::ofstream fout("apm.out");

    int32_t n, m;
    fin >> n >> m;

    for(int32_t i = 0; i != n; ++i)
        parent[i] = -1;

    for(int32_t i = 0; i != m; ++i) {
        Edge edge;
        fin >> edge.x >> edge.y >> edge.c;
        --edge.x; --edge.y;
        edges[i] = edge;
    }
    std::sort(edges, edges + m, Compare);

    int32_t nodeCount = 0;
    int64_t totalCost = 0;
    for(int32_t i = 0; i != m && nodeCount != n; ++i) {
        int32_t root1 = Root(edges[i].x);
        int32_t root2 = Root(edges[i].y);

        if(root1 == root2)
            continue;

        edgeUsed[i] = true;

        totalCost += edges[i].c;
        nodeCount += (!used[edges[i].x]) + (!used[edges[i].y]);

        used[edges[i].x] = true;
        used[edges[i].y] = true;

        Merge(root1, root2);
    }

    fout << totalCost << '\n' << (n - 1) << '\n';
    for(int32_t i = 0; i != m; ++i) {
        if(edgeUsed[i])
            fout << (edges[i].x + 1) << ' ' << (edges[i].y + 1) << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}