#include <fstream>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct nod
{
    int val,cost;
    nod *urm;
};
typedef nod *pnod;
pnod v[200003],p;
bool viz[200003];
int u,use[200003],m1[200003],m2[200003],nr,ct,n,m;
inline void ad(int x,int y,int c)
{
    p=new nod;
    p->urm=v[x]->urm;
    p->cost=c;
    p->val=y;
    v[x]->urm=p;
}
int minim,x1,y1;
inline int cauta(int nod)
{
    p=v[nod]->urm;
    minim=2000;
    while(p)
    {
        if(viz[p->val]==1)
        {
            if(p->cost<minim)
            {
               minim=p->cost;
               y1=p->val;
            }
        }
        p=p->urm;
    }
    ct+=minim;
    return y1;
}
int l1,c1;
pnod p1;
inline void cauta()
{
    int i;
    minim=2000;
    for(i=1;i<=u;i++)
    {
        p=v[use[i]]->urm;
        p1=v[use[i]];
        while(p)
        {
            if(viz[p->val]==0)
            {
                if(p->cost<minim)
                {
                    minim=p->cost;
                    l1=use[i];
                    c1=p->val;

                }
                p1=p;
                p=p->urm;
            }
            else
            {
                p1->urm=p->urm;
                p=p1->urm;
            }
        }
    }
    viz[c1]=1;
    ct+=minim;
    nr+=1;
    m1[nr]=l1;
    m2[nr]=c1;
    u+=1;
    use[u]=c1;
}
int main()
{
    int i,minim=2000,x,y,n1,n2,c;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        ad(x,y,c);
        ad(y,x,c);
        if(c<minim)
        {
            minim=c;
            n1=x;
            n2=y;
        }
    }
    viz[n1]=viz[n2]=1;
    ct=minim;
    m1[1]=n1;
    m2[1]=n2;
    nr=1;
    use[1]=n1;
    use[2]=n2;
    u=2;
    for(i=3;i<=n;i++)
    {
        cauta();
    }
    g<<ct<<'\n';
    g<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        g<<m1[i]<<" "<<m2[i]<<'\n';
    }
    return 0;
}