#include<fstream>
#include<algorithm>
#define alfa 200001
using namespace std;
typedef struct muchie{int x,y,c;};
int t[alfa],rez[alfa];
int m,n;
muchie l[alfa];
int tat(int x)
{
	while (t[x]!=x)
		x=t[x];
	return x;
}
int comp(muchie a, muchie b)
{
	return a.c<b.c;
}
int main()
{
	int i,j,x,y,s=0,k=0;
	ifstream in("apm.in");
	in>>n>>m;
	for (i=1;i<=n;i++)
		t[i]=i;
	for (i=1;i<=m;i++)
	in>>l[i].x>>l[i].y>>l[i].c;
	sort (l+1,l+m+1,comp);
	for (i=1;i<=n;i++)
	{
		x=l[i].x; x=tat(x);
		y=l[i].y; y=tat(y);
		if (x!=y)
		{
			t[x]=y;
			s+=l[i].c;
			rez[++k]=i;
		}
	}
	ofstream out("apm.out");
	out<<s<<'\n'<<k<<'\n';
	for (k;k>0;k--)
		out<<l[rez[k]].x<<" "<<l[rez[k]].y<<'\n';
}