#include <fstream>
#define MMAX 400001
#define NMAX 200001
#include<algorithm>
using namespace std;
ofstream g("apm.out");
struct muchie
{
    int a,b,c;
    bool ap;
};
bool compara(muchie aa,muchie bb)
{
    if(aa.c<bb.c)
        return true;
    else
        return false;
}
muchie muc[MMAX];
int n,m,costapm=0;
void kruskal()
{
    int componente[NMAX],nrmuchii=0,muchiecur,compmodif;
    sort(&muc[1],&muc[m+1],compara);
    for (int i=1;i<=n;++i)
        componente[i]=i;
    muchiecur=1;
    while(nrmuchii<(n-1))
    {
        if(componente[muc[muchiecur].a]!=componente[muc[muchiecur].b])
        {
            compmodif=componente[muc[muchiecur].b];
            for(int i=1;i<=n;++i)
                if(componente[i]==compmodif)
                    componente[i]=componente[muc[muchiecur].a];
            costapm+=muc[muchiecur].c;
            nrmuchii++;
            muc[muchiecur].ap=true;
        }
        muchiecur++;
    }
}

int main()
{
    ifstream f("apm.in");
    f>>n>>m;
    for(int i=1;i<=m;++i)
        f>>muc[i].a>>muc[i].b>>muc[i].c;
    kruskal();
    g<<costapm<<"\n"<<n-1<<"\n";
    for(int i=1;i<=m;++i)
    {
        if(muc[i].ap==true)
        {
            g<<muc[i].a<<" "<<muc[i].b;
            g<<"\n";
        }
    }
    f.close();
    g.close();
    return 0;
}