#include<fstream>
using namespace std;
long mc[400005][3],i,j,n,m,ind[400003],t[400005],h[200005],indcpy[200005];
ofstream g("apm.out");
bool cond(int i,int j)
{
	return(mc[i][2]<mc[j][2]);
}
int arb(int vf)
{
	while(t[vf])vf=t[vf];
	return vf;
}

void kruskal(int n)
{long k=1,nr=1,cost=0,v1=0,v2=0;
   do
   {
	do{ v1=arb(mc[ind[k]][0]); v2=arb(mc[ind[k]][1]); k++; } while(v1==v2);//caut muchie care uneste 2 arb diferiti 
	  k--;
	if(h[ v1 ]==h[ v2 ])//unesc arborii
	{
	    h[ v1 ]++;
		t[ v2 ] = v1;
	}
	else
	if(h[ v1 ]<h[ v2 ])//unesc arborii
	   t[ v1 ]  = v2;
	     else
	   t[ v2 ] = v1;
	indcpy[nr]=ind[k];
	nr++;
	cost+=mc[ind[k]][2];//initialize costul
	k++;
   }while(nr<=n-1);
   
   g<<cost<<"\n"<<n-1<<"\n";//afisez costul
   
   for(i=1;i<=n-1;i++)
		g<<mc[indcpy[i]][0]<<" "<<mc[indcpy[i]][1]<<"\n";//afisez muchiile
}

int main()
{
	ifstream f("apm.in");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>mc[i][0]>>mc[i][1]>>mc[i][2];
		ind[i]=i;
	}
	sort(ind+1,ind+m+1,cond);
	kruskal(n);
  f.close();g.close();
return 0;}