#include<fstream>
using namespace std;

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

struct nod{int n1,n2;nod *urm;};
nod *p,*u;

int const maxn=200005,maxm=400005;
int n,m,cost,nrm;
int x[maxm],y[maxm],c[maxm],t[maxn];

void cit()
{
	int i;
	
	fin>>n>>m;
	
	for(i=1;i<=m;i++)
		fin>>x[i]>>y[i]>>c[i];
	
}

int poz(int p,int u)
{
	int i,j,i1,j1,aux;
	
	i1=0; j1=-1;
	i=p; j=u;
	
	while(i<j)
	{	
		if(c[i]>c[j])
		{
			aux=x[i]; x[i]=x[j]; x[j]=aux;
			aux=y[i]; y[i]=y[j]; y[j]=aux;
			aux=c[i]; c[i]=c[j]; c[j]=aux;
			
			aux=-i1;
			i1=-j1;
			j1=aux;
	    }
		
		i+=i1;
		j+=j1;
	}
	
	return i;
} 
	
void quick(int p,int u)
{
	int k;
	
	if(p<u)
	{
		k=poz(p,u);
		quick(p,k-1);
		quick(k+1,u);
	}
}

void add(int nod1,int nod2)
{
	nod *q;
	
	q=new nod;
	
	q->n1=nod1;
	q->n2=nod2;
	q->urm=0;
	if(p==0)
		p=u=q;
	
	u->urm=q;
	u=q;
}


int search(int k)
{
	if(t[k]==k) return k;
	t[k]=search(t[k]);
	return t[k];
}

void kruskal()
{
	int i,j;
	int rx,ry;
	
	for(i=1;i<=n;i++)
		t[i]=i;
	
	for(i=1;i<=m;i++)
	{
		rx=search(x[i]);
		ry=search(y[i]);
		
		if( rx!=ry )
		{
			nrm++;
			add(y[i],x[i]);
			cost+=c[i];
			
			t[rx]=ry;
		}
	}

}


void afis()
{
	int i;
	nod *q;
	
	//fout<<"cost: "<<
	fout<<cost<<'\n';
	
	//fout<<"muchiile: ";
	fout<<nrm<<'\n';
	q=p;
	while(q)
	{
		fout<<q->n1<<" "<<q->n2<<'\n';
		
		q=q->urm;
	}
	
}


int main()
{
	cit();
	quick(1,m);
	kruskal();
	afis();
	
	fin.close();
	fout.close();
	return 0;
}