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

using namespace std;

struct Muchie {
    int u, v, cost;

    Muchie() {}
    Muchie(int x, int y, int w) : u(x), v(y), cost(w) {}

    bool operator<(const Muchie& m) const {
        return this->cost < m.cost;
    }
};

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

vector<int> h, tata;

int Find(int u) {
    if(tata[u] == 0) {
        return u;
    }
    return Find(tata[u]);
}

void Union(int u, int v) {
    int ru = Find(u);
    int rv = Find(v);

    if (ru == rv) {
        return;
    }

    if (h[ru] < h[rv]) {
        tata[ru] = rv;
    } else if (h[ru] == h[rv]) {
        tata[ru] = rv;
        h[rv]++;
    } else {
        tata[rv] = ru;
    }
}

vector<Muchie> kruskal(vector<Muchie> &muchii, int N, int &costTotal) {
    h = tata = vector<int>(N + 1, 0);
    costTotal = 0;

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

    vector<Muchie> apcm;
    for (auto& m : muchii) {
        if (Find(m.u) != Find(m.v)) {
            Union(m.u, m.v);
            costTotal += m.cost;
            apcm.push_back(m);
        }
    }

    return apcm;
}

int main() {

    int N, M;
    fin >> N >> M;

    vector<Muchie> muchii;
    for (int i = 0; i < M; i++) {
        int x, y, w;
        fin >> x >> y >> w;

        muchii.push_back(Muchie(x, y, w));
    }

    int costTotal = 0;
    vector<Muchie> apcm = kruskal(muchii, N, costTotal);

    fout << costTotal << endl;
    fout << apcm.size() << endl;
    for (auto& m : apcm) {
        fout << m.u << ' ' << m.v << endl;
    }
    return 0;
}