#include <stdio.h>
#define max 10000
#define inf 1000000000
int i,j,n,m,c[max][max],d[max],t[max],sol[max],cost,k,p,radacina=1,pmin,min,nr;
char u[max];
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++)
     for(j=1; j<=n; j++)
      if(i!=j) c[i][j]=inf;
    for(k=1; k<=m; k++)
    {
        scanf("%d%d%d",&i,&j,&p);
        c[i][j]=c[j][i]=p;
    }
    for(i=1; i<=n; i++)
     d[i]=c[radacina][i],t[i]=radacina;
    u[radacina]=1;
    while(1)
    {
        min=inf; pmin=-1;
        for(i=1; i<=n; i++)
         if(!u[i] && min>d[i])
          min=d[i],pmin=i;
        if(min==inf) break;
        u[pmin]=1;
        cost+=d[pmin];
        sol[pmin]=t[pmin]; ++nr;
        for(i=1; i<=n; i++)
         if(d[i]>c[pmin][i])
         {
             d[i]=c[pmin][i];
             t[i]=pmin;
         }
    }
    printf("%d\n",cost);
    printf("%d\n",nr);
    for(i=1; i<=n; i++)
     if(sol[i]!=0) printf("%d %d\n",sol[i],i);
    return 0;
}