#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

const int Mmax=4e5, Nmax=2e5+1;

int n, m, total, nrm;

int X[Mmax], Y[Mmax];

struct muchie{
    int x, y, c;
}v[Mmax];

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


struct DSU{
    int rep[Nmax], sz[Nmax];

    /// constructor pentru DSU
    DSU(int n){
        for (int i=1; i<=n; i++){
            rep[i]=i;
            sz[i]=1;
        }
    }

    /// functie care ne da radacina arborelui nodului "nod"
    int get_rep(int nod){
        /// cu path compression
        if (nod==rep[nod])
            return nod;
        else{
            // cod lungut
            /*
            int rnod=get_rep(rep[nod]);
            rep[nod]=rnod;
            return rnod;
            */
            return rep[nod]=get_rep(rep[nod]);
        }
    }

    /// functie prin care verificam daca nodurile "a" si "b" sunt in aceasi componenta
    bool same_comp(int a, int b){
        int ra=get_rep(a);
        int rb=get_rep(b);

        if (ra==rb)
            return 1;
        else return 0;
    }

    /// functie care combina multimile nodurilor "a" si "b"
    void join (int a, int b){
        int ra=get_rep(a);
        int rb=get_rep(b);

        /// cu small to large

        /// bagam pe b in a
        if (sz[ra]>sz[rb]){
            rep[rb]=ra;
            sz[ra]+=sz[rb];
        }
        /// bagam pe a in b
        else{
            rep[ra]=rb;
            sz[rb]+=sz[ra];
        }
    }
};

int main()
{
    fin>>n>>m;

    DSU dsu(n);

    for (int i=0; i<m; i++)
        fin>>v[i].x>>v[i].y>>v[i].c;

    sort (v, v+m, cmp);

    for (int i=0; i<m; i++){
        if (!dsu.same_comp(v[i].x, v[i].y)){
            total+=v[i].c;
            dsu.join(v[i].x, v[i].y);

            X[nrm]=v[i].x;
            Y[nrm]=v[i].y;
            nrm++;
        }
    }

    fout<<total<<'\n';
    fout<<nrm<<'\n';
    for (int i=0; i<nrm; i++)
        fout<<X[i]<<' '<<Y[i]<<'\n';

    return 0;
}