#include <fstream>
#include <iostream>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,i,j,k,x,y,z,s,nr,nod,cost=0;
short a[4][200005],v[10005],sol[3][10005];

void swap(int xx,int yy)
{
    int aux;
    aux=xx;
    xx=yy;
    yy=aux;
}


int main()
{
    f>>n>>m;
    for (i=1; i<=m;i++) {f>>x>>y>>z; a[1][i]=x;a[2][i]=y;a[3][i]=z;}

    for (i=1;i<=m-1;i++)
      for (j=i+1;j<=m;j++)
      {
          if (a[3][i]>a[3][j])
          {
              for (k=1;k<=3;k++)
              {
                swap (a[k][i],a[k][j]);
              }

          }
      }

for (i=1;i<=n;i++) {v[i]=i;}

for (i=1;i<=m;i++)
{
    if (v[a[1][i]] != v[a[2][i] ] )
    {
      nod= v[a[2][i]];
      v[a[2][i]]= v[a[1][i]] ;
      cost=cost+a[3][i];
      nr++;
      sol[1][nr]=a[1][i];
      sol[2][nr]=a[2][i];

      for (j=1;j<=n;j++)
      {
          if (v[j]==nod)
          {
              v[j]=v[a[1][i]];
          }
      }
    }
}

  g<<cost<<endl<<nr<<endl;
  for (i=1;i<=nr;i++)

  {
      g<<sol[1][i]<<" "<<sol[2][i]<<endl;
  }

}