#include <fstream>
#include <algorithm>
#define LE 400600
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int V[LE/2],father[LE/2],i,m,n,rez,k,A,B;
int ind[LE],x[LE],y[LE],cost[LE];
int cmp(int  a,int  b)
{
	return cost[a]<cost[b];
}
int root( int nod)
{
	while (father[nod]!=nod) nod=father[nod];
	return nod;
}
int uneste(int nod1)
{
	int noo;
	while (father[nod1]!=nod1)
		{
			noo=nod1;
			nod1=father[nod1];
			father[noo]=B;
	     }
}
int main()
{
	f>>n>>m;
	for(i=1;i<=m;++i){
		f>>x[i]>>y[i]>>cost[i];
     ind[i]=i;
     }

	sort(ind+1,ind+m+1,cmp);
	
	for(i=1;i<=n;++i) father[i]=i;
	
	for(i=1;i<=m;++i)
	{
		A=root(x[ind[i]]);B=root(y[ind[i]]);
		if (B!=A) 
		{
			uneste(x[ind[i]]);
			V[++k]=ind[i];
			father[A]=B;
			rez+=cost[ind[i]];
		}
	}
	
	g<<rez<<'\n'<<k<<'\n';
	for(i=1;i<=k;++i)
		g<<x[V[i]]<<" "<<y[V[i]]<<'\n';
	
	f.close();g.close();
	return 0;
}