#include<bits/stdc++.h>
#define P pair<int,int>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int NMAX = 100005;
vector<pair<int,int> > v[NMAX];
int N,M,este_in_apm[NMAX],dr[NMAX];

class heap{

    P t[NMAX];
    int N,este[NMAX];
    int fiu_st(int nod){

        return 2*nod;
    }
    int fiu_dr(int nod){

        return 2*nod + 1;
    }
    int tata(int nod){

        return nod / 2;
    }
    void in_sus(int nod){

        while(tata(nod) != 0 && t[nod].second < t[tata(nod)].second){
            swap(este[t[nod].first],este[t[tata(nod)].first]);
            swap(t[nod],t[tata(nod)]);
            nod = tata(nod);
        }
    }
    void in_jos(int nod){

        int fiu = nod;
        bool ok;
        do{
            ok = false;
            if(fiu_st(nod) <= N && t[nod].second > t[fiu_st(nod)].second)
                fiu = fiu_st(nod);
            if(fiu_dr(nod) <= N && t[fiu].second > t[fiu_dr(nod)].second)
                fiu = fiu_dr(nod);
            if(fiu != nod){
                swap(este[t[nod].first],este[t[fiu].first]);
                swap(t[fiu],t[nod]);
                ok = true;
                nod = fiu;
            }
        }while(ok);
    }
public:
    heap() : N(0)
    {
        for(int i = 1 ; i < NMAX ; ++i)
            este[i] = 0;
    }
    P minim(){
        return t[1];
    }
    void adauga(P elem){
        t[++N] = elem;
        este[elem.first] = N;
        in_sus(N);
    }
    void stergeMin(){
        este[t[1].first] = 0;
        t[1] = t[N];
        este[t[1].first] = 1;
        N--;
        if(N > 1)
            in_jos(1);
    }
    bool esteElem(int elem){
        if(este[elem])
            return true;
        return false;
    }
    bool schimbaValoare(int elem,int val){
        bool ok = false;
        int poz = este[elem];
        if(t[poz].second > val){
            t[poz].second = val;
            ok = true;
        }
        in_sus(poz);
        return ok;
    }
    void afis(){
        for(int i = 1 ; i <= N ; ++i)
            cout<<t[i].first<<" "<<t[i].second<<" ";
        cout<<"\n";
    }
    int size(){
        return N;
    }
};

int main()
{

    in>>N>>M;
    int a,b,c,costAPM = 0;
    heap H;
    for(int i = 1 ; i <= M ; ++i){
        in>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    vector<pair<P,int> > sol;
    int act = 1;
    este_in_apm[1] = 1;
    for(int j = 1 ; j < N ; ++j){
        for(int i = 0 ; i < v[act].size() ; ++i){
            int nod = v[act][i].first;
            int cost = v[act][i].second;
            if(H.esteElem(nod)){
                if(H.schimbaValoare(nod,cost))
                    dr[nod] = act;
            }
            else if(!este_in_apm[nod]){
                H.adauga(v[act][i]);
                dr[nod] = act;
            }
        }
        P urm;
        do{
            urm = H.minim();
            H.stergeMin();
        }while(este_in_apm[urm.first]);
        costAPM += urm.second;
        este_in_apm[urm.first] = 1;
        act = urm.first;
        sol.push_back(make_pair(make_pair(urm.first,dr[urm.first]),urm.second));
    }
    out<<costAPM<<"\n"<<N-1<<"\n";
    for(int i = 0 ; i < sol.size() ; ++i)
        out<<sol[i].first.first<<" "<<sol[i].first.second<<" "<<sol[i].second<<"\n";
    return 0;
}