#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,cost,s[400001][2];
int main()
{
	int i,j,xi,yi;
	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);
	for(i=1;i<=n;i++)cc[i]=i;
	int nr=0;i=1;
	while(nr!=n-1)
	{
		xi=L[i].x;
		yi=L[i].y;
		if(cc[xi]!=cc[yi])
		{
			cost+=L[i].z;
			L[i].luat=1;
			for(j=1;j<=n;j++)
				if(cc[j]==cc[xi])cc[j]=cc[yi];
			nr++;
				s[0][nr]=xi;
				s[1][nr]=yi;
		}
		i++;
	}
	g<<cost<<"\n"<<nr<<'\n';
	for(i=1;i<=nr;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;
}