#include <fstream>
#include <iostream>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,i,j,k,x,y,z,minnod,minn,min1,s,nr;
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]);
              }

          }
      }
    cout<<endl;

    /*for (i=1; i<=m;i++)
    {
        for (j=1;j<=3;j++)
        {
            cout<<a[j][i]<<" ";
        }
        cout<<endl;
    }*/
    minn=1000000;
    for (i=1;i<=m;i++)
    {
        if ((v[a[1][i]]==0) || (v[a[2][i]]==0)|| (v[a[1][i]]!=v[a[2][i]]) )
        {
          s=s+a[3][i];
          nr++;
          if (a[1][i]< a[2][i]){minnod=a[1][i];}else {minnod=a[2][i];}
          if  (minnod < minn) {min1=minn; minn=minnod;}
          if (v[a[1][i]]!=v[a[2][i]])
          {
            for (j=1;j<=n;j++)
            {
                if (v[j]==min1){v[j]=minn;}
            }
          }


          v[a[1][i]]=minn;
          v[a[2][i]]=minn;


          sol[1][nr]=a[1][i];sol[2][nr]=a[2][i];


        }


    }

  g<<s<<endl<<nr<<endl;
  for (i=1;i<=nr;i++)
  {
      g<<sol[1][i]<<" "<<sol[2][i]<<endl;
  }

}