//APM - Algoritmul lui Prim - 20 puncte Infoarena ??

#include <stdio.h>
#include <algorithm>
#define INF 20000

using namespace std;

FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");
int c[20001][20001],use[20001],sol[20001][2],m,n;
//int t[20001],cmin[20001];

long long ct;

void citire()
{
int i,j,k,cost;
fscanf(f,"%d %d",&n,&m);
for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
     if (j==i) c[i][j]=0;
     else c[i][j]=INF;

for(k=1;k<=m;k++)
  {fscanf(f,"%d %d %d",&i,&j,&cost);
   c[i][j]=c[j][i]=cost;
  }
fclose(f);
}

/*void prim(int x)
{
int i,j,k,mn,p;

for(i=1;i<=n;i++)
  {cmin[i]=c[x][i];
   t[i]=x;
  }
use[x]=1;

for (k=2;k<=n;k++)
  { mn=INF;
    for(i=1;i<=n;i++)
      if (!use[i] && cmin[i]<mn)
      {
        mn=cmin[i];
        p=i;
      }
    if (mn==INF) break;

    use[p]=1;
    ct+=mn;
    sol[k][0]=t[p];
    sol[k][1]=p;

    for(i=1;i<=n;i++)
      if (c[p][i]<cmin[i])
       {
        cmin[i]=c[p][i];
        t[i]=p;
       }
  }
}
*/

int main()
{int i,j,k,mn;
 citire();
 //prim(1);

 for(i=2;i<=n;i++) use[i]=1;
 for(k=2;k<=n;k++)
    {
        mn=INF;
        for(i=1;i<=n;i++)
        if(use[i])
          if(mn>c[use[i]][i])
           {
            mn=c[use[i]][i];
            j=i;
           }
      sol[k][0]=use[j];
      sol[k][1]=j;
      ct+=c[j][use[j]];
      for(i=1;i<=n;i++)
        if(use[i] && c[i][use[i]]>c[i][j]) use[i]=j;
      use[j]=0;
    }

 fprintf(g,"%lld\n%d\n",ct,n-1);
 for (i=2;i<=n;i++)
    fprintf(g,"%d %d\n",sol[i][0],sol[i][1]);
 return 0;
}