#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
#include <numeric>

using namespace std;

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

struct DSU {
    vector<int> parent;
    vector<int> sz;

    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        sz.assign(n + 1, 1);
    }

    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (sz[root_i] < sz[root_j]) {
                swap(root_i, root_j);
            }
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
        }
    }
};

void kruskal(int n, int m, priority_queue<tuple<int, int, int>,
    vector<tuple<int, int, int>>, greater<tuple<int, int, int>>>& edges);

int main() {
    int n, m;
    fin >> n >> m;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> edges;

    for (int i = 0; i < m; ++i) {
        int u, v, weight;
        fin >> u >> v >> weight;
        edges.push({weight, u, v});
    }

    kruskal(n, m, edges);

    return 0;
}

void kruskal(int n, int m, priority_queue<tuple<int, int, int>,
    vector<tuple<int, int, int>>, greater<tuple<int, int, int>>>& edges) {

    DSU dsu(n);
    long long total_cost = 0;
    int edges_used = 0;
    vector<pair<int, int>> mst_edges;

    while (!edges.empty() && edges_used < n - 1) {
        tuple<int, int, int> top_edge = edges.top();
        edges.pop();

        int weight = get<0>(top_edge);
        int u = get<1>(top_edge);
        int v = get<2>(top_edge);

        if (dsu.find(u) != dsu.find(v)) {
            dsu.unite(u, v);
            total_cost += weight;
            mst_edges.push_back({u, v});
            ++edges_used;
        }
    }

    fout << total_cost << '\n' << edges_used << '\n';
    for (const auto& edge : mst_edges) {
        fout << edge.first << ' ' << edge.second << '\n';
    }
}