#include <cstdio>

using namespace std;
FILE *in=fopen ("apm.in","r");
FILE *out=fopen ("apm.out","w");
const int M=250001,N=50001,INF=999999999;
int n,m,lst[N],vf[2*M],urm[2*M],q[2*M],cost[2*M],d[N],h[N],poz[N],nh,pred[N];
void adauga (int x,int y,int z)
{
    vf[++m]=y;
    cost[m]=z;
    urm[m]=lst[x];
    lst[x]=m;
}
void schimb (int p1,int p2)
{
    int aux=h[p1];
    h[p1]=h[p2];
    h[p2]=aux;
    poz[h[p1]]=p1;
    poz[h[p2]]=p2;
}
void urca(int p)
{
    while (p>1 && d[h[p]]< d[h[p/2]])
    {
        schimb (p,p/2);
        p/=2;
    }
}
void coboara (int p)
{
    int fs=2*p,fd=2*p+1,bun=p;
    if (fs<=nh && d[h[fs]]<d[h[bun]]) bun=fs;
    if (fd<=nh && d[h[fd]]<d[h[bun]]) bun=fd;
    if (bun!=p)
    {
        schimb (bun,p);
        coboara(bun);
    }
}
void stergeH (int p)
{
    schimb (p,nh--);
    urca(p);
    coboara(p);
}
void adaugaH (int x)
{
    h[++nh]=x;
    poz[x]=nh;
    urca(nh);
}
void afisare ()
{
    int s=0;
    for (int i=2;i<=n;i++)
        s+=d[i];
    fprintf (out,"%d\n%d\n",s,n-1);
    for (int i=2;i<=n;i++)
            fprintf(out,"%d %d\n",i,pred[i]);
}
void dijkstra (int x0)
{
    int x,y,c,pozitie;
    for (int i=1; i<=n; i++)
    {
        d[i]=INF;
        poz[i]=0;
    }
    nh=0;
    h[++nh]=x0;
    d[x0]=0;
    while (nh!=0)
    {
        x=h[1];

        //fprintf(out, "scot din H %d:\t cu costul %d\n", x, d[x]);
        stergeH(1);
        poz[x]=-1;
        pozitie=lst[x];
        while (pozitie!=0)
        {
            y=vf[pozitie];
            c=cost[pozitie];
            if (c<d[y] && poz[y]>=0)
            {
                d[y]=c;
                pred[y]=x;
                if (poz[y]==0) adaugaH(y);
                else urca(poz[y]);
            }
            pozitie=urm[pozitie];
        }
        //afisare();
    }
    afisare();
}
void citire ()
{
    int a;
    //printf ("incepe citirea\n");
    fscanf (in,"%d%d",&n,&a);
    //printf ("%d %d",n,a);
    for (int i=1;i<=a;i++)
    {
        int x,y,z;
        fscanf (in,"%d%d%d",&x,&y,&z);
        adauga(x,y,z);
        adauga (y,x,z);
    }
    //printf ("a citit");
    dijkstra(1);
}
int main()
{
    citire();
    return 0;
}