#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int x, y;
    int cost;
};

struct DSU {
    vector<int> parent, sz;

    DSU(int n = 0) {
        parent.resize(n + 1);
        sz.assign(n + 1, 1);
        for (int i = 1; i <= n; ++i)
            parent[i] = i;
    }

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

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

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].cost;

    sort(edges.begin(), edges.end(),
         [](const Edge &a, const Edge &b) {
             return a.cost < b.cost;
         });

    DSU dsu(N);
    long long totalCost = 0;
    vector<pair<int, int>> chosen;

    for (const auto& e : edges) {
        if (dsu.unite(e.x, e.y)) {
            totalCost += e.cost;
            chosen.push_back({e.x, e.y});
            if ((int)chosen.size() == N - 1)
                break;
        }
    }

    fout << totalCost << "\n";
    fout << chosen.size() << "\n";
    for (auto &p : chosen)
        fout << p.first << " " << p.second << "\n";

    return 0;
}