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

#define MAX_N 200005

int parent[MAX_N];
int rank[MAX_N];

void init_dsu(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }

    return parent[x];
}

bool unite(int x, int y) {
    x = find(x);
    y = find(y);

    if (x == y) {
        return false;
    }

    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else if (rank[x] > rank[y]) {
        parent[y] = x;
    } else {
        parent[y] = x;
        rank[x]++;
    }

    return true;
}

struct Edge {
    int x, y, cost;

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

struct MSTEdge {
    int x, y;

    MSTEdge(Edge edge) : x{edge.x}, y{edge.y} {}
};

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

    int n, m;
    fin >> n >> m;

    std::vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        fin >> edges[i].x >> edges[i].y >> edges[i].cost;
    }

    sort(edges.begin(), edges.end());
    init_dsu(n);

    std::vector<MSTEdge> mst_edges;
    intmax_t total_cost = 0;

    for (const Edge& e : edges) {
        if (unite(e.x, e.y)) {
            mst_edges.push_back(e);
            total_cost += e.cost;
        }

        if (mst_edges.size() == n - 1) {
            break;
        }
    }

    fout << total_cost << "\n";
    fout << mst_edges.size() << "\n";
    for (auto edge : mst_edges) {
        fout << edge.x << " " << edge.y << "\n";
    }
}