#include<iostream>
#include<fstream>
using namespace std;

typedef struct{int u,v,c;} muchie;
int l[30],n,m;
muchie e[30];

void citire()
{  int i;
   ifstream f("Apm.in");
   f>>n;
   f>>m;
   for(i=1;i<=m;i++)
      f>>e[i].u>>e[i].v>>e[i].c;
}

void afisare()
{
    int i;
    for(i=1;i<=n;i++)
        cout<<e[i].u<<" "<<e[i].v<<" "<<e[i].c<<endl;
}

int main()
{  int k,ultim,i,u,v,ct,ind,ms,lu,lv,c=0;
   muchie aux;
   ofstream g("Apm.out");
   citire();
   for(i=1;i<=n;i++)
      l[i]=i;
   ultim=m;
   while(ultim>1)
   {  k=0;
      for(i=1;i<=ultim-1;i++)
         if(e[i].c>e[i+1].c)
         {  aux=e[i];
            e[i]=e[i+1];
            e[i+1]=aux;
            k=1;}
   ultim=k;}
   cout<<k<<endl;
   cout<<"APM contine muchiile:"<<endl;
   ct=0;ms=0;ind=0;
   while(ms<n-1)
   {  do
      ind++;
      while(l[e[ind].u]==l[e[ind].v]);
      u=e[ind].u;
      lu=l[u];
      v=e[ind].v;
      lv=l[v];
      cout<<u<<"  "<<v<<endl;
      c++;
      ct=ct+e[ind].c;
      ms++;
      for(i=1;i<=n;i++)
        if(l[i]==lu)
      l[i]=lv;
   }
      cout<<"costul APM este:"<<ct;
      g<<ct<<endl;
      g<<c<<endl;
      for(i=1;i<=c;i++)
        g<<e[i].u<<" "<<e[i].v<<endl;
}