#include <fstream>
#define fs(x) x*2
#define fd(x) x*2+1
#define cfs(x) c[h[x*2]]
#define cfd(x) c[h[x*2+1]]
#define cst(x) c[h[x]]
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

typedef struct nod
{
    int inf,c;
    nod *urm;
} NOD;
typedef NOD *graf[100010];
graf G;

int n,m,v[100010],poz[100010];
int c[100010],h[200010],hh,from[100010],cost;

void citire()
{
    f>>n>>m;
    int a,b,c;
    NOD *p,*q;
    for(int i=0;i<m;i++)
    {
        f>>a>>b>>c;
        p=new NOD;p->inf=b;p->c=c; p->urm=G[a];G[a]=p;
        q=new NOD;q->inf=a;q->c=c; q->urm=G[b];G[b]=q;
    }
    f.close();
}

void sift(int i)
{
    int ok=1;
    while(ok&&i<=hh)
        if(cst(i)>cfs(i)&&fs(i)<=hh)
        {
            if(cst(i)>cfd(i)&&fd(i)<=hh)
            {
                int aux;
                if(cfs(i)<cfd(i))
                    aux=fs(i);
                else
                    aux=fd(i);
                swap(poz[h[i]],poz[aux]);
                swap(h[i],h[aux]);
                i=aux;
            }
            else
            {
                swap(poz[h[i]],poz[h[fs(i)]]);
                swap(h[i],h[fs(i)]);
                i=fs(i);
            }
        }
        else
        if(cst(i)>cfd(i)&&fd(i)<=hh)
        {
            swap(poz[h[i]],poz[h[fd(i)]]);
            swap(h[i],h[fd(i)]);
            i=fd(i);
        }
        else
            ok=0;
}

void percolate(int i)
{
    int ok=1;
    while(ok&&i>1)
        if(cst(i)<cst(i/2))
        {
            swap(poz[h[i]],poz[h[i/2]]);
            swap(h[i],h[i/2]);
            i/=2;
        }
        else
            ok=0;
    sift(i);
}

void addElem(int x,int cst,int f)
{
    if(poz[x])
    {
        if(cst<c[x])
        {
            cost=cost-c[x]+cst;
            c[x]=cst;
            from[x]=f;
        }
        return ;
    }
    h[++hh]=x;
    poz[x]=hh;
    c[x]=cst;
    cost+=c[x];
    from[x]=f;
    percolate(hh);
}

void Delete(int x)
{
    v[h[x]]=1;
    h[x]=h[hh--];
    h[hh+1]=0;
    percolate(x);
    poz[x]=0;
}

void addNode(int x)
{
    for(NOD *i=G[x];i;i=i->urm)
        if(!v[i->inf]) addElem(i->inf,i->c,x);
}

int main()
{
    citire();
    addNode(1);v[1]=1;
    for(int i=2;i<=n;i++)
    {
        int x=h[1];
        Delete(1);
        addNode(x);
    }
    g<<cost<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)
        g<<i<<' '<<from[i]<<'\n';
    return 0;
}