//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],t[20001],cmin[20001],sol[20001][2],m,n;
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;
 citire();
 prim(1);
 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;
}