#include<fstream>
using namespace std;
#define MX 200001
struct Muchie{int x,y,c;}Muc[2*MX];
long long Smin;
long N,M;
int cc[MX],G[2*MX],L;

void read()
{
	ifstream f ("apm.in");
	f>>N>>M;
	for(long i=1;i<=M;i++)
		f>>Muc[i].x>>Muc[i].y>>Muc[i].c;
	f.close();
	for(long i=1;i<=N;i++) cc[i]=i;
}

void sort()
{
	Muchie aux;
	for(long i=1;i<M;i++)
		for(long j=i+1;j<=M;j++)
			if(Muc[i].c>Muc[j].c)
			{
				aux=Muc[i];
				Muc[i]=Muc[j];
				Muc[j]=aux;
			}
}

int main()
{
	read();
	sort();
	long k=1,Mi,Ma;
	while(L<N-1)
	{
		if(cc[Muc[k].x]!=cc[Muc[k].y])
		{
			G[++L]=k;
			Smin+=Muc[k].c;
			Mi=min(cc[Muc[k].x],cc[Muc[k].y]);
			Ma=max(cc[Muc[k].x],cc[Muc[k].y]);
			for(long i=1;i<=N;i++) if(cc[i]==Ma) cc[i]=Mi;
		}
		k++;
	}

	ofstream g("apm.out");
	g<<Smin<<'\n'<<L<<'\n';
	for(long i=1;i<=L;i++)
		g<<Muc[G[i]].y<<' '<<Muc[G[i]].x<<'\n';
	g.close();

	return 0;
}