#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <utility>

struct Edge {
    int from, to, weight;
};

void quicksort(std::vector<Edge> &myV, int left, int right) {
    if (left >= right) {
        return;
    }

    int l(left), r(right);
    int pos = left + std::rand() % (right - left);
    Edge pivot = myV[pos];

    while (l < r) {
        while (myV[l].weight < pivot.weight) {
            l++;
        }
        while (myV[r].weight > pivot.weight) {
            r--;
        }
        if (l <= r) {
            std::swap(myV[l], myV[r]);
            l++;
            r--;
        }
    }
    quicksort(myV, left, r);
    quicksort(myV, l, right);
}

struct Node {
    int parent, val, level;
};

int find_parent(std::vector<Node> &nodes, int node) {
    if (node != nodes[node].parent) {
        nodes[node].parent = find_parent(nodes, nodes[node].parent);
    }
    return nodes[node].parent;
}

void make_union(std::vector<Node> &nodes, int a, int b) {
    a = find_parent(nodes, a);
    b = find_parent(nodes, b);
    if (nodes[a].level == nodes[b].level) {
        nodes[a].level++;
        nodes[b].parent = a;
    } else if (nodes[a].level < nodes[b].level) {
        nodes[a].parent = b;
    } else {
        nodes[b].parent = a;
    }
}

int main() {
    std::srand(std::time(nullptr));
    std::ifstream fileIn("apm.in");
    std::ofstream fileOut("apm.out");

    int nV, nM;

    fileIn >> nV >> nM;

    std::vector<Edge> edges;
    std::vector<Node> nodes(nV + 1);

    for (int i(1); i <= nV; i++) {
        nodes[i].parent = i;
        nodes[i].val = i;
        nodes[i].level = 1;
    }

    Edge aux;

    for (int i(0); i < nM; i++) {
        aux = Edge();
        fileIn >> aux.from >> aux.to >> aux.weight;
        edges.push_back(aux);
    }

    quicksort(edges, 0, nM - 1);

    std::vector<Edge> outEdges;
    int sum = 0;
    for (Edge edge : edges) {
        if (find_parent(nodes, edge.from) != find_parent(nodes, edge.to)) {
            sum += edge.weight;
            outEdges.push_back(edge);
            make_union(nodes, edge.from, edge.to);
        }
    }

    fileOut << sum << '\n' << outEdges.size() << '\n';

    for (Edge edge : outEdges) {
        fileOut << edge.from << ' ' << edge.to << '\n';
    }

    fileIn.close();
    fileOut.close();
    return 0;
}