#include <iostream>
#include <fstream>

#include <vector>
#include <algorithm>


using namespace std;

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

struct Muchie {
    int a, b, cost;

    bool operator<(const Muchie& other) {
        return cost < other.cost;
    }
};

vector<Muchie> listaMuchii;
vector<Muchie> muchiiSelectate;

vector<int> tata;
vector<int> h;

int find(int nod) {
    int i = nod;
    while (i != tata[i]) {
        i = tata[i];
    }

    tata[nod] = i;
    return i;
}

void reuneste(int x, int y) {
    int rx = find(x);
    int ry = find(y);
    if (rx == ry) {
        return;
    }

    if (h[rx] > h[ry]) {
        tata[ry] = rx;
    }
    else {
        if (h[rx] == h[ry]) {
            h[ry]++;
        }
        tata[rx] = ry;
    }

}

int main() {

    int n, m;
    fin >> n >> m;

    tata.resize(n+1);
    h.resize(n+1, 0);
    for (int i=1; i<=n; i++) {
        tata[i] = i;
    }

    for (int i=1; i<=m; i++) {
        int x, y, cost;
        fin >> x >> y >> cost;
        listaMuchii.push_back({x,y,cost});
    }

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

    int costTotal = 0;

    for (Muchie muchie : listaMuchii) {
        if (find(muchie.a) != find(muchie.b)) {
            reuneste(muchie.a, muchie.b);
            costTotal += muchie.cost;
            muchiiSelectate.push_back(muchie);
        }
    }

    fout << costTotal << endl;
    fout << muchiiSelectate.size() << endl;
    for (Muchie m : muchiiSelectate) {
        fout << m.a << " " << m.b << endl;
    }

    return 0;
}