#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchii
{
	int x;
	int y;
	short z;
	int luat;
};
muchii L[400001];
int cmp(muchii a,muchii b)
{
	return a.z<b.z;
}

int cc[200001],n,m,nr,t[400001];
int s[2][400001];
int arb(int nod)
{
	while(t[nod])nod=t[nod];
	return nod;
}
int main()
{
	int i,j,xi,yi,k,sum=0;
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>L[i].x>>L[i].y>>L[i].z;
		/* for(j=1;j<i;j++)
              if(L[j].x==L[i].x&&L[j].y==L[i].y)
                  if(L[i].z>L[j].z)
                 { i--;m--;}
                  else
                      {L[j].z=L[i].z;i--;m--;}*/
	}
	sort(L+1,L+m+1,cmp);

	k=1;
	do
	{
		while(arb(L[k].x)==arb(L[k].y))k++;
		nr++;
		s[0][nr]=L[k].x;
		s[1][nr]=L[k].y;
		sum+=L[k].z;
		if(cc[L[k].x]==cc[L[k].y])
		{
			t[L[k].x]=L[k].y;
		}
		else t[L[k].y]=L[k].x;
		k++;
	}while(nr<n-1);
	g<<sum<<'\n'<<n-1<<'\n';
	for(i=1;i<n-1;i++)
		g<<s[0][i]<<" "<<s[1][i]<<'\n';
	/*for(i=1;i<=m;i++)
		g<<L[i].z<<" ";
	g<<'\n';
	for(i=1;i<=m;i++)
		g<<L[i].luat<<" ";
	g<<'\n';
	for(i=1;i<=n;i++)
		g<<cc[i]<<" ";
	g<<n<<"<-";*/
	return 0;
}