#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;
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 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)
	{
		
		if (root(x[ind[i]])!=root(y[ind[i]]) )
		{
			father[root(x[ind[i]])]=root(y[ind[i]]);
			V[++k]=ind[i];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;
}