#include <cstdio>

using namespace std;
const int N=200001;
const int M=400001;
int lst[N],urm[M],vf[M],cost[N],d[N],h[N],poz[M],pred[M];
int p,n,m,nh;
void ad(int x,int y,int c)
{
    p++;
    vf[p]=y;
    urm[p]=lst[x];
    lst[x]=p;
    cost[p]=c;
}
void schimba(int x,int y)
{
    int aux=h[x];
    h[x]=h[y];
    h[y]=aux;
    poz[h[x]]=x;
    poz[h[y]]=y;
}
void urca(int x)
{
    if(x==1)
        return ;
    if(d[h[x/2]]>d[h[x]])
    {
        schimba(x,x/2);
        urca(x/2);
    }
}
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]])
    {
        schimba(bun,p);
        coboara(bun);
    }
}
int scoate()
{
    int a=h[1];
    schimba(1,nh);
    urca(1);
    coboara(1);
    nh--;
    poz[a]=-1;
    return a;
}
int main()
{
    FILE *in,*out;
    in=fopen("apm.in","r");
    out=fopen("apm.out","w");
    int i,j,c,x,y,total=0;
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        ad(x,y,c);
        ad(y,x,c);
    }
    for(i=1;i<=n;i++)
    {
        d[i]=9999999;
        h[i]=i;
        poz[i]=i;
    }
    d[1]=0;
    nh=n;
    while(nh!=0)
    {
        x=scoate();
        p=lst[x];
        while(p!=0)
        {
            y=vf[p];
            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<=n;i++)
        total=total+d[i];
    fprintf(out,"%d\n%d\n",total+1,n-1);
    for(i=2;i<=n;i++)
        fprintf(out,"%d %d\n",i,pred[i]);
    return 0;
}