#include<fstream>
#include<algorithm>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct apm
{
	int nod1,nod2,cost;
};

int c,i,nr,n,m,x,y,z,T[200001],R[200001];
apm a[400001],sol[400001];

bool cmp(apm x,apm y)
{
	return (x.cost<y.cost);
}

int tata(int x)
{
	if (x==T[x]) return x;
	return tata(T[x]);
}

void uneste(int x,int y)
{
	if (R[x]>R[y]) T[y]=x;
		else T[x]=y;
	if (R[x]==R[y]) R[y]++;
}

int main()
{
	in>>n>>m;
	
	for (i=1;i<=m;i++)
		in>>a[i].nod1>>a[i].nod2>>a[i].cost;
	
	sort(a+1,a+m+1,cmp);
	
	for (i=1;i<=n;i++)
	{
		T[i]=i;
		R[i]=1;
	}
	
	for (i=1;i<=m;i++)
	{
		if (tata(a[i].nod1)==tata(a[i].nod2)) continue;
		
		uneste(tata(a[i].nod1),tata(a[i].nod2));
		c+=a[i].cost;
		sol[++nr]=a[i];
	}
	
	out<<c<<'\n'<<nr<<'\n';
	for (i=1;i<=nr;i++)
		out<<sol[i].nod1<<' '<<sol[i].nod2<<'\n';
}