#include<fstream>
#include<algorithm>
#define asdf 32386
using namespace std;
typedef struct muchie {int x,y,c;};
muchie m[asdf];
int z,n,k;
int t[asdf],niv[asdf],sol[asdf],total,nr;
int tat(int nod)
{
	while (t[nod]!=nod)
		nod=t[nod];
	return nod;
}
int cmp(muchie a, muchie b){	return a.c<b.c;}

void citire()
{
	int i;
	ifstream in("apm.in");
	in>>n>>z;
	//in>>k;
	for (i=1;i<=z;i++)
		in>>m[i].x>>m[i].y>>m[i].c;
	in.close();
	for (i=1;i<=n;i++)
		t[i]=i;
	sort(m+1,m+z+1,cmp);
}
void solve()
{
	int xx,yy,i;
	for (i=1;i<=z;i++)
	{
		xx=tat(m[i].x);
		yy=tat(m[i].y);
		if (xx!=yy)
		{
			total+=m[i].c;
			sol[++nr]=i;
			if (niv[xx]>niv[yy])
				t[yy]=xx;
			else if (niv[xx]<niv[yy])
				t[xx]=yy;
			else if (niv[xx]==niv[yy])
			{
				t[yy]=xx;
				niv[xx]++;
			}
		}
	}
}
void afis()
{
	int i;
	ofstream out("apm.out");
	out<<total<<'\n'<<nr<<'\n';
	for (i=1;i<=nr;i++)
		out<<m[sol[i]].x<<" "<<m[sol[i]].y<<'\n';
	out.close();
}
	

int main()
{
	citire();
	solve();
	afis();
}