#include <fstream>
#include <algorithm>
#define vmax 400001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{int in, fn, cost;};
muchie lista[vmax];
int ctmin, n,m;
int cc[vmax/2+2];
int nrm;//nr muchii selectate
muchie sol[vmax];//lista muchiilor selectate
bool comp(muchie a, muchie b)
{
   return a.cost<b.cost;
}

void citire();
void parcurgere();
void afisare();
int main()
{
    citire();
    parcurgere();
    afisare();
    return 0;
}
void citire()
{
   fin>>n>>m;
   for (int i=1; i<=m; i++)
      fin>>lista[i].in>>lista[i].fn>>lista[i].cost;
}
void parcurgere()
{
   int i,j,k=1,x;
   muchie cr;
   sort(lista+1, lista+m+1, comp);
   for (i=1; i<=n; i++)
      cc[i]=i;
   while (nrm<n-1)
      {

         cr=lista[k];
         k++;
         if (cc[cr.in]!=cc[cr.fn])
            {
               ctmin+=cr.cost;
               nrm++;
               sol[nrm]=cr;
               x=cr.in;
               for (i=1; i<=n; i++)
                  if (cc[i]==cc[x])
                     cc[i]=cc[cr.fn];
            }
      }
}
void afisare()
{
   fout<<ctmin<<'\n'<<nrm<<'\n';
   for (int i=1; i<=nrm; i++)
      fout<<sol[i].in<<' '<<sol[i].fn<<'\n';
}