#include <stdio.h>

using namespace std;

const int N = 200001;
const int M = 400001;
const int MAX = 99999999;

int h[N],poz[N],nh; //heap-ul si inversul heap-ului
int lst[N],val[2*M],urm[2*M],cost[2*M],nr; // graful
int d[N],pred[N];

void graf(int x, int y, int c)
{
    nr++;
    val[nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
    cost[nr]=c;
}

int aux;
void interschimba(int p, int q)
{
    aux=h[p];
    h[p]=h[q];
    h[q]=aux;
    poz[h[p]]=p;
    poz[h[q]]=q;
}

void urca(int p)
{
    //printf("il urc pe %d\n",h[p]);
    if(p==1) return;
    if(d[h[p]]<d[h[p>>1]])
    {
        interschimba(p,p>>1);
        urca(p>>1);
    }
}

void coboara(int p)
{
    int fs=2*p,fd=2*p+1,bun;
    if(fs>nh) return;
    if(fs<=nh) bun=fs;
    if(fd<=nh && d[h[fs]]>d[h[fd]]) bun=fd;
    if(d[h[bun]]<d[h[p]])
    {
        interschimba(bun,p);
        coboara(bun);
    }
}

int scoate()
{
    int x=h[1];
    interschimba(1,nh);
    nh--; poz[x]=-1;
    coboara(1);
    return x;
}

int main()
{
    FILE *in=fopen("apm.in","r");
    FILE *out=fopen("apm.out","w");

    int m,n,i,x,y,c,p,total;
    fscanf(in,"%d%d",&n,&m);
    for(i=0;i<m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        graf(x,y,c);
        graf(y,x,c);
    }

    //initializari
    d[1]=0;
    for(i=2;i<=n;i++) d[i]=MAX;
    for(i=1;i<=n;i++) h[i]=poz[i]=i;
    nh=n;

    while(nh>0)
    {
        //printf("NOU PAS\n");
        x=scoate();
        p=lst[x];
        while(p!=0)
        {
            y=val[p];
            //printf("p=%d, y=%d\n",p,y);
            c=cost[p];
            if(c<d[y] && poz[y]!=-1)
            {
                d[y]=c;
                urca(poz[y]);
                pred[y]=x;
            }
            p=urm[p];
        }
        //for(i=1;i<=nh;i++)
           //fprintf(out,"(%d,%d) ",h[i],d[h[i]]);
        //fprintf(out,"\n");
    }

    total=0;
    for(i=1;i<=n;i++)
        total+=d[i];
    fprintf(out,"%d\n%d\n",total,n-1);
    for(i=2;i<=n;i++)
        fprintf(out,"%d %d\n",i,pred[i]);

    return 0;
}