#include <iostream.h>
#include <fstream.h>

#define IN "apm.in"
#define OUT "apm.out"
#define maxx 200005

ifstream fin(IN);
ofstream fout(OUT);

struct muchii
{
 int c1;
 int c2;
 int cost;
 int use;
}m[maxx];
int g[maxx];
int n,mm;
int sol;

void citire();
void afisare();
void init();
void alg();
void act(int x,int y);

void quick(int s,int d);
int pozi(int s,int d);

int main()
{
 citire();
  fin.close();

 quick(1,mm);
 alg();

 afisare();
  fout.close();
  
return 0;
}

void citire()
{
 int i;

 fin>>n>>mm;
  for(i=1;i<=mm;i++)
  {
   fin>>m[i].c1;
   fin>>m[i].c2;
   g[m[i].c1]++;
   g[m[i].c2]++;
   fin>>m[i].cost;
   m[i].use=1;
  }
}

void afisare()
{
 int i,nr=0;

 for(i=1;i<=mm;i++)
  if(m[i].use==1)
   {
    sol=sol+m[i].cost;
    nr++;
   }
   
 fout<<sol<<endl;
 fout<<nr<<endl;
  for(i=1;i<=mm;i++)
   if(m[i].use==1)
    fout<<m[i].c1<<" "<<m[i].c2<<endl;
}

void quick(int s,int d)
{
 if(s<d)
 {
  int k;
  k=pozi(s,d);
  quick(s,k-1);
  quick(k+1,d);
 }
}

int pozi(int s,int d)
{
 int i1=0;
 int j1=-1;
 int i=s;
 int j=d;
 muchii aux;
 int ax;

 while(i<j)
 {
  if(m[i].cost<m[j].cost)
  {
   aux=m[i];
   m[i]=m[j];
   m[j]=aux;
                         
   ax=i1;
   i1=-j1;
   j1=-ax;
  }
  i=i+i1;
  j=j+j1;
 }
 return i;
}


void alg()
{
 int cont=mm-n+1;
 int i;
 
 for(i=1;i<=mm && cont;i++)
  if( (g[m[i].c1]>1 && g[m[i].c2]>1) && (g[m[i].c1]>2 || g[m[i].c2]>2) )
  {
   m[i].use=0;
   cont--;
   g[m[i].c1]--;
   g[m[i].c2]--;
  }
                  
 if(cont>0)
  for(i=1;i<=mm;i++)
   if(m[i].use==1)
   {
    m[i].use=0;
    break;        
   }
}