#include<fstream>
#define nmax 200001

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n,comp[nmax],m;
int valid[nmax];
long costapm;

struct muchie
   {int x,y,cost;
   };
muchie l[nmax];

void citire()
{int i;
fin>>n>>m;
for(i=1;i<=m;i++)
  fin>>l[i].x>>l[i].y>>l[i].cost;
}

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

void kruskal()
{int i,j,k=0,maxim,minim;
for(i=1;i<=n;i++)
   comp[i]=i;
for(i=1;i<=m && k<n-1;i++)
    if(comp[l[i].x]!=comp[l[i].y])
      {k++;
       costapm+=l[i].cost;
       valid[i]=1;
       if(comp[l[i].x]>comp[l[i].y])
          {maxim=comp[l[i].x];
           minim=comp[l[i].y];
          }
        else
          {maxim=comp[l[i].y];
           minim=comp[l[i].x];
          }
       for(j=1;j<=n;j++)
         if(comp[j]==maxim) comp[j]=minim;
      }
fout<<costapm<<'\n';
fout<<k<<'\n';
for(i=1;i<=m;i++)
  if(valid[i])
    fout<<l[i].x<<" "<<l[i].y<<'\n';
}

int main()
{citire();
ordonare();
kruskal();
fin.close();
fout.close();
return 0;
}