#include<stdio.h>
#include<string.h>
#define Inf 0x3f3f3f3f
#define Nmax 200003
FILE*f=fopen("apm.in","r");
FILE*g=fopen("apm.out","w");
int H[Nmax],N; // H[i] - nodul aflat pe pozitia i in heap
int poz[Nmax]; // poz[i] - pozitia in heap a nodului i
int c[Nmax]; // c[i] - costul nodului i
int viz[Nmax];
int Nod[Nmax]; // Nod[i] - nodul de la care vine elementul de pe pozitia i
int n,m;
int sol[2][Nmax], nr;
struct Graf{int vf,cst; Graf *urm;};
Graf *G[Nmax];
inline void add(int x, int y, int cst)
 {
 Graf *q;
 q=new Graf;
 q->vf = y;
 q->cst = cst;
 q->urm = G[x];
 G[x]=q;
 }
void read()
 {
  fscanf(f,"%d%d",&n,&m);
  int a,b,c;
  while(m--)
   {
    fscanf(f,"%d%d%d",&a,&b,&c);
    add(a,b,c); add(b,a,c);
   }
 }
inline void swap(int f, int t)
 {
  int aux;
  aux=Nod[f]; Nod[f] = Nod[t]; Nod[t]=aux;
  aux=poz[H[f]]; poz[H[f]]=poz[H[t]]; poz[H[t]]=aux;
  aux=H[f]; H[f]=H[t]; H[t]=aux;
  
 }
void print()
 {
  int i,j;
  fprintf(g,"%d\n",nr-1);
  for(i=2;i<=nr;++i) fprintf(g,"%d %d\n",sol[0][i],sol[1][i]);
 }
void downheap(int t) // duc in jos elementul de pe pozitia k
 {
  int f;
  do
   {
     f=0;
     if(2*t <= N) f=2*t;
     if(2*t+1 <= N && c[H[f]] > c[H[2*t+1]]) f=2*t+1;
     if(c[H[f]] > c[H[t]]) f=0;
     if(f)
      {
       swap(t,f);
       t=f;
      }
   }
  while(f);
 }
void upheap(int f)
 {
  int t=f/2;
  while(t && c[H[t]] > c[H[f]])
   {
    swap(t,f);
    t=t/2; f=f/2;
   }
 }
int s;
void apm()
 {
  int i,p, nod;
  memset(c,Inf,sizeof(c));
  memset(poz,-1,sizeof(poz));
  c[1]=0;
  H[1] = 1;
  poz[1] = 1;
  Nod[1] = -1;
  N=1;
  Graf *q;
  for(i=1;i<=n;++i)
   {
    p = H[1]; // introduc nodul p
    nod = Nod[1];  // am muchia (nod,p)
    s+=c[p];
    sol[0][++nr] = p; sol[1][nr] = nod;
    viz[p] = 1;

    // elimin varful p din heap

    H[1] = H[N];
    Nod[1] = Nod[N];
    poz[H[1]] = 1;
    N--;
    downheap(1);

    //fac update pt nodurile care nu sunt in arbore

    for(q=G[p];q;q=q->urm)

      if(!viz[q->vf] && c[q->vf] > q->cst)
        {
          c[q->vf] = q->cst;
          if(poz[q->vf] == -1)
            {
              N++;
              poz[q->vf] = N;
              Nod[N] = p;
              H[N] = q->vf;
              upheap(N);
            }
          else
           {
            Nod[poz[q->vf]] = p;
            upheap(poz[q->vf]);
           }
        }

    }
 fprintf(g,"%d\n",s);
 }
int main()
 {
  read();
  apm();
  print();
  return 0;
  }