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


class muchie
{
    int nod1, nod2, c;
public:
    muchie(int nod1, int nod2, int c): nod1(nod1), nod2(nod2), c(c){}
    bool operator < (const muchie& str) const
    {
        return (c < str.c);
    }

    int getNod1() const {
        return nod1;
    }

    int getNod2() const {
        return nod2;
    }

    int getC() const {
        return c;
    }
};

class Graf {
    vector<int> tata, h;
    vector<muchie> muchii;
    int n, m;
public:

    Graf(const vector<int> &tata1, const vector<int> &h1,
         const vector<muchie> &muchii1, int n, int m) :
            tata(tata1), h(h1), muchii(muchii1), n(n), m(m) {

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

    int Reprez(int u) {
        while (tata[u] != 0)
            u = tata[u];
        return u;
    }

    bool Reuneste(int nod1, int nod2){
        int r1 = Reprez(nod1), r2 = Reprez(nod2);
        if(r1!=0 && r1 == r2)
            return false;
        if(h[r1] > h[r2])
            tata[r2] = r1;
        else{
            tata[r1] = r2;
            if(h[r1] == h[r2])
                h[r2] = h[r2] + 1;
        }
        return true;
    }

    vector<muchie> APM(){
        vector<muchie> sol;
        sort(muchii.begin(), muchii.end());

        for(auto &mch : muchii){
            if(Reuneste(mch.getNod1(), mch.getNod2()))
                sol.push_back(mch);
        }
        return sol;
    }
};

int main() {
    vector<int> tata, h;
    vector<muchie> muchii;
    int n, m;
    fin>>n>>m;
    tata.resize(n+1);
    h.resize(n+1);

    for(int i=0; i<m; i++){
        int nod1, nod2, c;
        fin>>nod1>> nod2>> c;
        muchii.emplace_back(nod1, nod2, c);
    }

    Graf g(tata, h, muchii, n, m);
    vector<muchie> apm = g.APM();
    int sum=0;
    for(auto elem:apm)
        sum+= elem.getC();
    fout<<sum<<endl<<apm.size()<<endl;
    for(auto elem: apm)
        fout<<elem.getNod1()<<" "<<elem.getNod2()<<endl;

    return 0;
}