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

using namespace std;

int parent[200005];
int rnk[200005];

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rnk[a] < rnk[b])
            swap(a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b])
            rnk[a]++;
    }
}

struct Edge {
    int x, y, c;
    bool operator<(const Edge& other) const {
        return c < other.c;
    }
};

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

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

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

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

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

    long long total_cost = 0;
    vector<pair<int, int>> mst_edges;

    for (int i = 0; i < m; ++i) {
        int x = edges[i].x;
        int y = edges[i].y;
        int c = edges[i].c;

        if (find_set(x) != find_set(y)) {
            union_sets(x, y);
            total_cost += c;
            mst_edges.push_back({x, y});
            if (mst_edges.size() == n - 1)
                break;
        }
    }

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

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

    return 0;
}