//Algoritmul lui Prim
#include<fstream>
#define Nmax 8000
#define infinit 20000

using namespace std;

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

short int c[Nmax][Nmax],s[Nmax];
short int cmin[Nmax],pre[Nmax],n,m;
long costul=0;

struct muchie
  {int x,y;
  };
muchie L[Nmax];

void citire()
{int i,j,x,y,cost;
fin>>n>>m;
for(i=1;i<n;i++)
  for(j=i+1;j<=n;j++)
    {c[i][j]=infinit;
    c[j][i]=infinit;
    }
for(i=1;i<=m;i++)
  {fin>>x>>y>>cost;
   c[x][y]=cost;
   c[y][x]=cost;
  }
for(i=1;i<=n;i++)
  {cmin[i]=c[1][i];
   pre[i]=1;
  }
}

void prim()
{long i,k=1,min,v;
s[1]=1;
while(k<=n-1)
  {min=infinit;
   for(i=1;i<=n;i++)
     if(!s[i] && cmin[i]<min)
       {min=cmin[i];
        v=i;
       }
   s[v]=1;
   L[k].x=pre[v];
   L[k].y=v;
   k++;
   costul=costul+min;
   for(i=1;i<=n;i++)
     if(s[i]==0 && cmin[i]>c[v][i])
        {cmin[i]=c[v][i];
         pre[i]=v;
        }
  }
fout<<costul<<'\n';
fout<<n-1<<'\n';
for(i=1;i<=n-1;i++)
  fout<<L[i].x<<" "<<L[i].y<<'\n';
}

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