#include <fstream>
#include <algorithm>
#include <vector>
std::ifstream fin("apm.in");
std::ofstream fout("apm.out");

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

bool comp(muchie a, muchie b){
    return a.c < b.c;
}

int main()
{
    int n, m, s;

    std::vector<int> t;
    std::vector<muchie> muc;
    std::vector<muchie> subarb;

    fin >> n >> m;

    muchie decoy;
    for(int i = 0; i < m; fin >> decoy.x >> decoy.y >> decoy.c, muc.push_back(decoy), i++);
    for(int i = 0; i <= n; t.push_back(i), i++);

    sort(muc.begin(), muc.end(), comp);

    s = 0;
    for(int i = 0; i < m; ++i)
        if(t[muc[i].x] != t[muc[i].y])
        {
            s += muc[i].c;
            int arb1 = t[muc[i].x], arb2 = t[muc[i].y];
            for(int j = 1; j <= n; ++j)
                if(t[j] == arb2)
                    t[j] = arb1;
            subarb.push_back(muc[i]);
        }
    fout << s << std::endl << subarb.size() << std::endl;
    for(auto much : subarb)
        fout << much.x << ' ' << much.y << std::endl;

    fin.close();
    fout.close();
    return 0;
}