#include<fstream>
using namespace std;
#include<algorithm>
struct muchie{
  int i,j;
  int cost;
  friend bool operator<(const muchie &a,const muchie &b)
  {
	  return a.cost<b.cost;
  }
};
 muchie v[400004];
 int n,m,t[200002],a[200002],na=0,h[200002];
 
 int radacina(int x)
 {
   int y=x,tmp;
   while(t[x])
    x=t[x];
   while(t[y])
     tmp=t[y],t[y]=x,y=tmp;
	return x;
  }
   
 int main()
 {
   ifstream fin("apm.in");
   ofstream fout("apm.out");
   fin>>n>>m;
   for(int i=1;i<=m;i++)
       fin>>v[i].i>>v[i].j>>v[i].cost;
   sort(v+1,v+m+1);
  // for(int i=1;i<=m;i++)
      // fout<<v[i].i<<" "<<v[i].j<<" "<<v[i].cost<<endl;
   for(int i=1;i<=m;i++)
   {
      int ri=radacina(v[i].i),rj=radacina(v[i].j);
	  if(ri!=rj){
	     a[na++]=i;
	     if(h[ri]<h[rj])
			t[ri]=rj;
		 else
	        if(h[ri]>h[rj])
	          t[rj]=ri;
	        else
		   t[ri]=rj,  ++h[rj];
	}
} 
 int s=0;
 for(int i=0;i<na;i++)
  s+=v[a[i]].cost;
 fout<<s<<"\n"<<na<<endl;
 for(int i=0;i<na;i++)
   fout<<v[a[i]].i<<" "<<v[a[i]].j<<endl;
 return 0;
}