#include <stdio.h>
#include <stdlib.h>

int v[400002][3];
int v2[200002];
int v3[200002][2];

int FindSef(int i){
  if(v2[i]==i){
    return i;
  }
  return FindSef(v2[i]);
}

void PunemSef(int i,int x){
  if(v2[i]!=i){
    PunemSef(v2[i],x);
  }
  v2[i]=x;
}

void myqsort( int begin, int end ) {
  int aux, b = begin, e = end,
    pivot = v[(begin + end) / 2][2]; // poate fi orice pozitie intre begin si end - 1

  while (v[b][2] < pivot) // cauta primul element mai mare sau egal cu pivotul
    b++;

  while (v[e][2] > pivot) // cauta primul element mai mic sau egal cu pivotul
    e--;

  while( b < e ) { // daca indicii nu s-au atins
    aux = v[b][2];    // interschimba elementele la pozitiile b si e
    v[b][2] = v[e][2];
    v[e][2] = aux;
    aux = v[b][0];    // interschimba elementele la pozitiile b si e
    v[b][0] = v[e][0];
    v[e][0] = aux;
    aux = v[b][1];    // interschimba elementele la pozitiile b si e
    v[b][1] = v[e][1];
    v[e][1] = aux;

    do // cauta primul element mai mare sau egal cu pivotul
      b++;
    while (v[b][2] < pivot);

    do // cauta primul element mai mic sau egal cu pivotul
      e--;
    while (v[e][2] > pivot);
  }

  // acum [begin..e] sint mai mici sau egale cu pivotul
  if ( begin < e )
    myqsort(begin, e);
  // si [e+1..end] sint mai mari sau egale cu pivotul
  if ( e + 1 < end )
    myqsort(e + 1, end);
}
int main(){
  int n,m,i,s,j;
  FILE *fin,*fout;
  fin=fopen("apm.in","r");
  fout=fopen("apm.out","w");
  fscanf(fin,"%d%d",&n,&m);

  for(i=0;i<m;i++){
    fscanf(fin,"%d",&v[i][0]);
    fscanf(fin,"%d",&v[i][1]);
    fscanf(fin,"%d",&v[i][2]);
  }

  myqsort(0,m-1);

  for(i=1;i<=n;i++){
    v2[i]=i;
  }
  s=0;
  j=0;
  for(i=0;i<m;i++){
    if(FindSef(v[i][0])!=FindSef(v[i][1])){
      s+=v[i][2];
      PunemSef(v[i][0],FindSef(v[i][1]));
      v3[j][0]=v[i][0];
      v3[j][1]=v[i][1];
      j++;
    }
  }

  fprintf(fout,"%d\n%d\n",s,j);
  j--;
  while(j>=0){
    fprintf(fout,"%d %d\n",v3[j][0],v3[j][1]);
    j--;
  }





  fclose(fin);
  fclose(fout);
  return 0;
}