//Algorimul lui Kruskal pentru determinarea
//arborelui de cost minim 50 de puncte pe infoarena
//timp depasit
#include<fstream.h>
#define Nmax 200001
#define Mmax 400001

int n,m,componenta[Nmax],k; //componenta va retine componenta conexa din care
long suma;                //face parte nodul i

struct muchie              //numarul de muchii ale arborelui
  {unsigned int x,y;
   int cost;
  };
muchie a[Mmax];   //a = lista muchiilor grafului neorintat conex

struct muchie_fara_cost
  {unsigned int x,y;
  };
muchie_fara_cost L[Mmax];                          //L = lista muchiilor arborelui partial de cost minim

void citire()
{ifstream fin("apm.in");
fin>>n>>m;
for(int i=1;i<=m;i++)
  {fin>>a[i].x>>a[i].y>>a[i].cost;
   componenta[i]=i;
  }
fin.close();
}

void det_arbore_de_cost_minim()
{int i,v1,v2,j;
for(i=1;i<=m && k<n-1;i++)
   if(componenta[a[i].x]!=componenta[a[i].y])
     {k++;
      L[k].x=a[i].x;
      L[k].y=a[i].y;
      suma=suma+a[i].cost;
      if(componenta[a[i].x]>componenta[a[i].y])
          {v1=componenta[a[i].y]; //valoarea cu care trebuie inlocuit v2
           v2=componenta[a[i].x];
          }
        else
           {v1=componenta[a[i].x];
            v2=componenta[a[i].y];
           }
      for(j=1;j<=n;j++)
        if(componenta[j]==v2)
          componenta[j]=v1;
     }
}

void ordonare()
{int i,j;
muchie aux;
for(i=1;i<m;i++)
  for(j=i+1;j<=m;j++)
    if(a[i].cost>a[j].cost)
       {aux=a[i];
       a[i]=a[j];
       a[j]=aux;
       }
}

void afisare()
{ofstream fout("apm.out");
fout<<suma<<'\n';
fout<<n-1<<'\n';
for(int i=1;i<=k;i++)
  fout<<L[i].x<<" "<<L[i].y<<'\n';
fout.close();
}

int main()
{citire();
ordonare();
det_arbore_de_cost_minim();
afisare();
return 0;
}