//Algoritmul lui Kruskal de determinare a unui APM

#include <stdio.h>
#define Mmax 4500
#define Nmax 100

int n,m;
// n reprezinta numarul de noduri iar m numarul de muchii din graful G

struct muchie
      {
       double cst;
       int x,y;
      } L[Mmax], Lfin[Nmax-1];
//L este o un vector de structuri de forma x,y,c ce reprezinta muchiile din garf
//x,y - nodurile extremitati ale muchiei
// c - costul muchiei
//Lfin reprezinta lista cu muchiile finale

int CompCon[Nmax];
double Cost;

void read(void); /* citeste datele de intrare in structura data in enunt */
void init(void); /* initializeaza vectorul ce tine evidenta componentelor conexe */
void CombHeap(int ,int); /* combina doua heap-uri */
void CreareHeap(void); /* creeaza un heap (in acest caz un MinHeap */
void ExtractHeap(int); /* extrage elementul din radacina heap-ului (elementul minim) */
void kruskal(void); /* realizeaza algoritmul lui Kruskal cu implementare de heap-uri */
void calculate_cost(void); /*calculeaza costul final al arborelui partial de cost minim 
insumand costurile muchiilor selectate */
void write(void); /* afiseaza in fisierul de iesire costul arborelui partial de cost 
minim si muchiile selectate ce formeaza acest arbore */

void read(void)
{
  FILE *f;
  int i;
  double aux;
  f = fopen("apm.in", "rt");

  fscanf(f,"%d\n",&n);
  fscanf(f,"%d\n",&m);

  for (i=0; i<m; i++)
       {
         fscanf (f,"%d %d",&L[i].x,&L[i].y);
         fscanf (f,"%lf", &aux);
         L[i].cst = aux;
         L[i].x--; L[i].y--;
       }
  fclose(f);
}

void init(void)
{
  int i;
  for (i=0; i<n; i++) CompCon[i] = i+1;
  }

void CombHeap(int i, int n)
{
  int fiu, tata;
  struct muchie aux;
  tata = i; fiu = 2*i;
  while (fiu<n)
       {
        if (fiu<n-1)
              fiu = L[fiu].cst<L[fiu+1].cst?fiu:fiu+1;
        if (L[tata].cst>L[fiu].cst)
              {
                aux = L[tata]; L[tata] = L[fiu]; L[fiu] = aux;
                tata = fiu; fiu *= 2;
              }
          else break;
       }
}

void CreareHeap(void)
{
  int i;
  for (i = m/2 - 1; i>=0; i--)
       CombHeap(i,m);
}

void ExtractHeap(int n)
{
  int tata,fiu;
  struct muchie aux;
  tata = 1; fiu = 2;
  L[tata] = L[n];
         
  if (fiu<n)
   do
       {
         if (fiu+1<n && L[fiu+1].cst<L[fiu].cst) fiu++;
         if (L[tata].cst<L[fiu].cst)
                {
                  aux = L[tata];
                  L[tata] = L[fiu];
                  L[fiu] = aux;
                  tata = fiu;
                  fiu *= 2;
                }
           else break;
       }
   while (fiu<n);
}

void kruskal(void)
{
  int i, j, k;
  CreareHeap();
  for (i=0, j=0; i<m && j<n; i++)
       {
         if (CompCon[L[i].x]!=CompCon[L[i].y])
               {
                 Lfin[j++] = L[i];
                 for (k=0; k<n; k++)
                        if (CompCon[k] == CompCon[L[i].x])
                                CompCon[k] = CompCon[L[i].y];
               }
               ExtractHeap(n-j+1);
       }
}

void calculate_cost()
{
  int i;
  for (i=0; i<n-1; i++)
       Cost += Lfin[i].cst;
}

void write(void)
{
  FILE *f;
  int i;
  f = fopen("apm.out","wt");

  fprintf(f,"%lf\n",Cost);

  for (i=0; i<n-1; i++)
        fprintf(f,"%d %d\n",Lfin[i].x+1,Lfin[i].y+1);

  fclose(f);
}


int main()
{
  read();
  init();
  kruskal();
  calculate_cost();
  write();
  return 0;
}