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

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

struct Edge {
    int u, v, cost;

    bool operator < (const Edge & other) {
        return cost < other.cost;
    }
};

int getParent (std::vector<std::pair<int, int>> & parent, int a) {
    int aux = a;
    while (parent[a].first != -1)
        a = parent[a].first;

    int root = a; a = aux;
    while (parent[a].first != -1) {
        aux = parent[a].first;
        parent[a].first = root;
        a = aux;
    }
    return root;
}

void MakeUnion (std::vector<std::pair<int, int>> & parent, int a, int b) {
    a = getParent (parent, a), b = getParent (parent, b);
    if (a != b) {
        if (parent[a].second < parent[b].second)
            std::swap (a, b);
        if (parent[a].second == parent[b].second)
            parent[a].second += 1;
        parent[b].first = a;
    }
}

int main () {
    int n, m; fin >> n >> m;
    std::vector<Edge> edges(m);
    for (int i = 0; i < m; i += 1) {
        fin >> edges[i].u >> edges[i].v >> edges[i].cost;
        edges[i].u -= 1, edges[i].v -= 1;
    }

    std::sort (edges.begin (), edges.end ());

    std::vector<std::pair<int, int>> parent(n, {-1, 1});

    std::vector<std::pair<int, int>> edgeSol;

    int sum = 0, number = 0;

    for (int i = 0; i < m; i += 1) {
        int node1 = edges[i].u;
        int node2 = edges[i].v;

        if (getParent (parent, node1) != getParent (parent, node2)) {
            MakeUnion (parent, node1, node2); sum += edges[i].cost;
            number += 1; edgeSol.emplace_back (std::make_pair (node1, node2));
        }
    }

    fout << sum << '\n' << number << '\n';
    for (auto & it : edgeSol)
        fout << it.first + 1 << ' ' << it.second + 1 << '\n';
    return 0;
}