#include<fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,i,T[200010],rx,ry,nr,cost,u[400010];
struct muchie{
	int x,y,c;
}v[400010];
int cmp(const muchie &a,const muchie &b)
{
	return a.c<b.c;
}	
int rad(int x)
{
	while(T[x]>0)
		x=T[x];
	return x;
}
int main()
{
	f>>n>>m;
	for(i=1;i<=n;i++)
		T[i]=-1;
	for(i=1;i<=m;i++)
		f>>v[i].x>>v[i].y>>v[i].c;
	sort(v+1,v+m+1,cmp);
	for(i=1;i<=m;i++)
	{
		rx=rad(v[i].x);
		ry=rad(v[i].y);
		if(rx!=ry)
			{
				if(T[rx]>T[ry])
					{
						T[ry]+=T[rx];
						T[rx]=ry;
					}
				else 
					{
						T[rx]+=T[ry];
						T[ry]=rx;
					}
				nr++;
				cost+=v[i].c;
				u[nr]=i;
			}
		if(nr==n-1) break;
	}
	g<<cost<<"\n"<<nr<<"\n";
	for(i=1;i<=n-1;i++)
		g<<v[u[i]].x<<" "<<v[u[i]].y<<"\n";
	
	return 0;
}