// Kruskal de 100 puncte
#include <fstream>
#include <algorithm>
using namespace std; 
ifstream f("apm.in"); ofstream g("apm.out");
int n,m,r1,r2,T[200002],sol[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(!T[x]) return x;
	T[x]=radacina(T[x]);
	return T[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)
			{sol[++k]=i; cost+=v[i].c;
			 T[r1]+=T[r2];	T[r2]=r1;
			}
	}
	g<<cost<<'\n'<<k<<'\n'; 
	for(i=1; i<=k; i++) g<<v[sol[i]].ei<<' '<<v[sol[i]].ef<<'\n'; 
	g.close(); return 0;
}