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

using namespace std;

struct muchie
{
    int x, y, c;
};

bool operator <(const muchie &m1, const muchie &m2)
{
    return (m1.c < m2.c);
}

int radacina(int x, vector <int> &t) {
    if (t[x] == 0) {
        return x;
    }
    t[x] = radacina(t[x], t); // compactarea drumurilor
    return t[x];
}

void reuniune(int x, int y, vector <int> &t, vector <int> &nr) {
    int rx = radacina(x, t);
    int ry = radacina(y, t);
    if (nr[x] < nr[y]) {
        t[rx] = ry;
        nr[ry] += nr[rx];
    } else {
        t[ry] = rx;
        nr[rx] += nr[ry];
    }
}

bool aceeasi_multime(int x, int y, vector <int> &t) {
    return (radacina(x, t) == radacina(y, t));
}

int main() {
    ifstream in("apm.in");
    ofstream out("apm.out");
    int n, m;
    in >> n >> m;
    vector <int> t(n + 1, 0);
    vector <int> nr(n + 1, 1);
    vector <muchie> vm(m);
    for (int i = 0; i < m; i++) {
        in >> vm[i].x >> vm[i].y >> vm[i].c;
    }
    sort(vm.begin(), vm.end());
    int cost = 0;
    vector <bool> in_apm(m, false);
    for (int i = 0; i < m; i++)
    {
        if (!aceeasi_multime(vm[i].x, vm[i].y, t))
        {
            cost += vm[i].c;
            in_apm[i] = true;
            reuniune(vm[i].x, vm[i].y, t, nr);
        }
    }
    out << cost << "\n" << n - 1 << "\n";
    for (int i = 0; i < m; i++)
    {
        if (in_apm[i])
        {
            out << vm[i].x << " " << vm[i].y << "\n";
        }
    }
    in.close();
    out.close();
    return 0;
}