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

using namespace std;

const int nmax = 100000;
vector<pair<pair<int, int>, int>> g;

ifstream fin("apm.in");
ofstream gout("apm.out");
int r[nmax + 1], r1, r2, n, m;

void initializare(int u) {
    r[u] = u;
}

int reprezentant(int u) {
    while (r[u] != u) {
        u = r[u];
    }
    return u;
}

void reuneste(int u, int v) {
    r1 = reprezentant(u);
    r2 = reprezentant(v);
    r[r2] = r1;
}

void Kruskal() {
    for (int v = 1; v <= n; v++)
        initializare(v);

    int nrmsel = 0;
    int costTotal = 0;
    vector<pair<int, int>> arbore;

    for (auto edge : g) {
        int u = edge.first.first;
        int v = edge.first.second;
        if (reprezentant(u) != reprezentant(v)) {
            reuneste(u, v);
            nrmsel = nrmsel + 1;
            costTotal += edge.second;
            arbore.push_back({u, v});
            if (nrmsel == n - 1)
                break;
        }
    }

    gout << costTotal << "\n";
    gout << nrmsel << "\n";
    for (auto edge : arbore) {
        gout << edge.first << " " << edge.second << "\n";
    }
}

int main() {
    fin >> n >> m;
    while (m--) {
        int x, y, cost;
        fin >> x >> y >> cost;
        g.push_back({{x, y}, cost});
    }

    sort(g.begin(), g.end(), [](const auto& a, const auto& b) {
        return a.second < b.second;
    });

    Kruskal();

    fin.close();
    gout.close();

    return 0;
}