#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

void citire(std::vector<std::vector<std::pair<int, int> > > &graf, int &n) {
    int m;
    int u, v, w;
    std::ifstream f("apm.in");
    f >> n >> m;
    graf.resize(n);
    while (m--) {
        f >> u >> v >> w;
        graf[u - 1].emplace_back(v - 1, w);
        graf[v - 1].emplace_back(u - 1, w);
    }
    f.close();
}

void prim() {
    std::vector<std::vector<std::pair<int, int> > > graf;
    int n;
    citire(graf, n);

    std::vector tata(n, -1), d(n, INT_MAX);
    std::vector inArbore(n, false);
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<> > q;

    std::vector<std::pair<int, int> > muchii;
    int nrNoduri = 0;
    int cost = 0;

    d[0] = 0;
    q.emplace(d[0], 0);
    while (!q.empty()) {
        const int dist = q.top().first;
        const int u = q.top().second;
        q.pop();

        if (dist > d[u]) continue;

        inArbore[u] = true;

        if (tata[u] != -1)
            muchii.emplace_back(u, tata[u]);
        cost += d[u];

        if (++nrNoduri == n)
            break;

        for (const auto &[v, w]: graf[u])
            if (!inArbore[v] && w < d[v]) {
                d[v] = w;
                tata[v] = u;
                q.emplace(w, v);
            }
    }
    // if (nrNoduri != n) {
    // std::cout << "Nu exista";
    // return;
    // }

    std::ofstream g("apm.out");
    g << cost << "\n";
    g << n - 1 << "\n";
    for (const auto& [i, j]: muchii)
        g << i + 1 << " " << j + 1 << "\n";
    g.close();
}

int main() {
    prim();
    return 0;
}