#include<fstream.h>
ifstream fin("apm.in");
ofstream fout("apm.out");

#define max 400

int n,mu,poz[max],sum;
struct nod{int c1,c2,cost;}muc[100];

void citire()
{fin>>n>>mu;
for(int i=1;i<=mu;i++)
  fin>>muc[i].c1>>muc[i].c2>>muc[i].cost;
}
int pozitie(int a,int b);
void quick(int st,int dr)
{if(st<dr)
  {int k;
   k=pozitie(st,dr);
   quick(st,k);
   quick(k+1,dr);
   }

}
void act(int x,int y)
{int i;
  for(i=1;i<=n;i++)
    if(poz[i]==x)poz[i]=y;

}

void minim()
{int i=1,aux;

  while(i<=mu)
  {if(poz[muc[i].c1]!=poz[muc[i].c2])
    {aux=poz[muc[i].c1];
     poz[muc[i].c1]=poz[muc[i].c2];
     muc[i].cost=0;
     act(aux,poz[muc[i].c1]);
     }
   i++;
  }

}

int pozitie(int st,int dr)
{int ii=0,jj=-1,a=st,b=dr,aux;
 while(a<b)
  {if(muc[a].cost>muc[b].cost)
    {nod p;
    p=muc[a];
    muc[a]=muc[b];
    muc[b]=p;

    aux=ii;
    ii=-jj;
    jj=-aux;

    }
   a+=ii;
   b+=jj;

  }
return a;
}
void afisare()
{int i,nr=0;
  for(i=1;i<=mu;i++)
    if(muc[i].cost!=0)
     {sum+=muc[i].cost;
      nr++;
      }
  fout<<sum<<'\n'<<nr<<'\n';
   for(i=1;i<=mu;i++)
    if(muc[i].cost)
     fout<<muc[i].c1<<" "<<muc[i].c2<<'\n';
 }



int main()
{citire();
 quick(1,mu);
 int i;
 for(i=1;i<=n;i++)poz[i]=i;
 poz[0]=n;

 minim();

 afisare();


 fin.close();
 fout.close();
 return 0;
 }