#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]); // path compression
    }

    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() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].x >> edges[i].y >> edges[i].cost;
    }

    // sortam muchiile dupa 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;   // muchiile din arbore

    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;
        }
    }

    // La problemele astea graful e garantat conex,
    // deci avem N-1 muchii.
    cout << totalCost << "\n";
    cout << chosen.size() << "\n";
    for (auto &p : chosen) {
        cout << p.first << " " << p.second << "\n";
    }

    return 0;
}