#include <fstream>
using namespace std;
#define NMAX 400001
long m,i,n,cost,nr;
ifstream f("apm.in");
ofstream g("apm.out");
bool viz[NMAX/2],ok[NMAX];
struct Muchie
 {
 long x,y;
 int c;
 } M[NMAX];
void read()
 {
 f>>n>>m;
 for(i=1;i<=m;i++)
  f>>M[i].x>>M[i].y>>M[i].c;
 }
void swap(Muchie &x,Muchie &y)
 {
 Muchie ax=x;
 x=y;
 y=ax;
 }
void qsort(long l,long r)
 {
 long i,j;
 j=l-1;
 for(i=l;i<=r;i++)
  if(M[i].c<=M[r].c)
   swap(M[i],M[++j]);
 if(l<j-1)
  qsort(l,j-1);
 if(j+1<r)
  qsort(j+1,r);
 }
void solve()
 {
 qsort(1,m);
 long i;
 for(i=1;i<=m;i++)
  {
  if(!viz[M[i].x]||!viz[M[i].y])
   {
   viz[M[i].x]=viz[M[i].y]=1;
   ok[i]=1;
   cost+=M[i].c;
   nr++;
   }
  }
 }
void show()
 {
 g<<cost<<endl<<nr<<endl;
 long i;
 for(i=1;i<=m;i++)
  if(ok[i])
   g<<M[i].x<<" "<<M[i].y<<endl;
 }
int main()
 {
 read();
 solve();
 show();
 return 0;
 }