#include<fstream.h>
#define inf 1500
#define infm inf*(inf-1)/2

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

int a[inf],c[inf],n,m;
struct nod{ int e,f,cost;
	   };
nod g[infm];


void citire()
{int i;
 fin>>n>>m;
 for(i=1;i<=m;i++)
 fin>>g[i].e>>g[i].f>>g[i].cost;
 for(i=1;i<=n;i++) c[i]=i;

 }


void afisare(int s)
{int i,costarb=0;
 for(i=1;i<=s;i++)
 {fout<<g[a[i]].e<<" "<<g[a[i]].f<<" ";
  fout<<g[a[i]].cost<<"\n";
  costarb+=g[a[i]].cost;
  }
 fout<<costarb<<"\n";
 }


int poz(int li,int ls)
{int i=li,j=ls,i1=0,j1=-1,t;
 nod r;
 while(i<j)
 {if(g[i].cost>g[j].cost)
  {r=g[i];
   g[i]=g[j];
   g[j]=r;
   t=i1;
   i1=-j1;
   j1=-t;
   }
  i+=i1;
  j+=j1;
  }
 return i;
 }


void quick(int li,int ls)
{int k;
 if(li<ls)
 {k=poz(li,ls);
  quick(li,k-1);
  quick(k+1,ls);
  }
 }


int main()
{int i,j,min,max,s=0;
 citire();
 quick(1,m);
 for(i=1;i<=m;i++)
 fout<<g[i].cost<<" ";
  fout<<"\n";

 for(i=1;s<n-1;i++)
 if(c[g[i].e]!=c[g[i].f])
  {s++;
   a[s]=i;
   if(c[g[i].e]<c[g[i].f])
   {min=c[g[i].e];
    max=c[g[i].f];
    }
    else{min=c[g[i].f];
	 max=c[g[i].e];
	 }
   for(j=1;j<=n;j++)
   if(c[j]==max) c[j]=min;
   }
 afisare(s);

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