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

int main()
{
    int n, m, s;
    bool nesor;
    struct muchie{
        int x, y, c;
    };

    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++);

    do{
        nesor = false;
        for(int i = 0; i < m - 1; ++i)
            if(muc[i].c > muc[i + 1].c)
                iter_swap(muc.begin() + i, muc.begin() + i + 1), nesor = true;
    }while(nesor);

    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;
}