// Kruskal de 70 puncte
#include <fstream>
#include <algorithm>
using namespace std; 
ifstream f("apm.in"); ofstream g("apm.out");
int n,m,r1,r2,arb[200002],a[200002];
struct muchie {int ei,ef,c;} v[400002];
int cmp(const muchie &a,const muchie &b) {return a.c<b.c;}
int radacina(int x)
{	if(!arb[x]) return x;
	arb[x]=radacina(arb[x]);
	return arb[x];
}
/*
inline int radacina(int x)
{	while(arb[x]>0) x=arb[x];
	return x;
}
*/
int main(void)
{	register int i,k=0,cost=0;
	f>>n>>m;
	for(i=1;i<=m;i++) f>>v[i].ei>>v[i].ef>>v[i].c; 
	sort(v+1,v+m+1,cmp);
	for(i=1;i<=m && k<n-1;i++)
		{r1=radacina(v[i].ei); r2=radacina(v[i].ef);
		 if(r1!=r2)
			{a[++k]=i; cost+=v[i].c;
			 arb[r1]+=arb[r2];	arb[r2]=r1;
			}
	}
	g<<cost<<'\n'<<k<<'\n'; 
	for(i=1; i<=k; i++) g<<v[a[i]].ei<<' '<<v[a[i]].ef<<'\n'; 
	g.close(); return 0;
}