#include <fstream>
#include <queue>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
struct varf
{
    int val,cost;
    varf *urm;
} *g[200100];
struct muchie
{
    int a,b,c;
    friend bool operator < (const muchie&,const muchie&);
} muc[200100];
bool operator < (const muchie& m1,const muchie& m2)
{
    return m1.c>m2.c;
}
priority_queue <muchie,vector<muchie>,less<muchie> > coada;
int n,m,use[200100],nr=1,costmin;
int main()
{
    int a,b,c,i;
    muchie aux;
    varf *p;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        p=new varf;
        p->cost=c;
        p->val=b;
        p->urm=g[a];
        g[a]=p;
        p=new varf;
        p->cost=c;
        p->val=a;
        p->urm=g[b];
        g[b]=p;
    }
    fin.close ();
    use[1]=1;
    for (p=g[1];p;p=p->urm)
    {
        aux.a=1;
        aux.b=p->val;
        aux.c=p->cost;
        coada.push (aux);
    }
    while (nr<n)
    {
        do
        {
            aux=coada.top();
            coada.pop();
        }
        while (use[aux.a]&&use[aux.b]);
        muc[nr++]=aux;
        costmin+=muc[nr-1].c;
        if (use[muc[nr-1].a])
        {
            use[muc[nr-1].b]=1;
            for (p=g[muc[nr-1].b];p;p=p->urm)
                if (!use[p->val])
                {
                    aux.a=muc[nr-1].b;
                    aux.b=p->val;
                    aux.c=p->cost;
                    coada.push(aux);
                }
        }
        else
        {
            use[muc[nr-1].b]=1;
            for (p=g[muc[nr-1].a];p;p=p->urm)
                if (!use[p->val])
                {
                    aux.a=muc[nr-1].a;
                    aux.b=p->val;
                    aux.c=p->cost;
                    coada.push(aux);
                }
        }
    }
    fout<<costmin<<'\n'<<n-1<<'\n';
    for (i=1;i<n;i++)
        fout<<muc[i].a<<' '<<muc[i].b<<'\n';
    fout.close ();
    return 0;
}