/*#include<fstream.h>

int h[200200],hh[200200],ver[800800],leg[800800],start[200200],cost[800800],L,n,m,lat[200200],dist[200200];

int ls(int nod)
{
	return nod<<1;
}
int rs(int nod)
{
	return 1+(nod<<1);
}
int fa(int nod)
{
	return nod>>1;
}
void ex(int i, int j)
{
	int aux=h[i];
	h[i]=h[j];
	h[j]=aux;
}
void sift(int nod)
{
	int son;
	do
	{
		son=0;
		if(ls(nod)<=L)
		{
			son=ls(nod);
			if(rs(nod)<=L&&dist[h[rs(nod)]]<dist[h[son]])
				son=rs(nod);
			if(dist[h[son]]>=dist[h[nod]])
				son=0;
		}
		if(son)
		{
			hh[h[son]]=nod;
			hh[h[nod]]=son;
			ex(son,nod);
			nod=son;
		}
	}
	while(son);
}
void percolate(int nod)
{
	int safe=h[nod],key=nod;
	while(dist[h[fa(key)]]>dist[safe]&&fa(key)>=1)
	{
		h[key]=h[fa(key)];
		hh[h[fa(key)]]=key;
		key=fa(key);
	}
	h[key]=safe;
	hh[safe]=key;
}
int extract()
{
	int key=h[1];
	hh[h[L]]=1;
	h[1]=h[L--];
	sift(1);
	hh[key]=0;
	return key;
}
int main()
{
	int i,k=0,x,y,c,u,t,nod,pampam=0,sol1[200200],sol2[200200];
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		ver[++k]=y;
		leg[k]=start[x];
		start[x]=k;
		cost[k]=c;
		ver[++k]=x;
		leg[k]=start[y];
		start[y]=k;
		cost[k]=c;
	}
	u=(1<<30);
	for(i=2;i<=n;i++)
	{
		dist[i]=u;
		h[++L]=i;
		hh[i]=L;
	}
	t=start[1];
	while(t)
	{
		dist[ver[t]]=cost[t];
		lat[ver[t]]=1;
		percolate(hh[ver[t]]);
		t=leg[t];
	}
	for(i=2;i<=n;i++)
	{
		nod=extract();
		pampam+=dist[nod];
		sol1[i]=lat[nod];
		sol2[i]=nod;
		t=start[nod];
		while(t)
		{
			if(dist[ver[t]]>cost[t])
			{
				dist[ver[t]]=cost[t];
				lat[ver[t]]=nod;
				percolate(hh[ver[t]]);
			}
			t=leg[t];
		}
	}
	g<<pampam<<'\n'<<n-1<<'\n';
	for(i=2;i<=n;i++)
		g<<sol1[i]<<' '<<sol2[i]<<'\n';
	return 0;
}
*/

#include<fstream.h>

int z[200200],h[400400],n,m,x[400400],y[400400],c[400400],pampam,sol[200200],k;

int comp(int i)
{
	if(z[i]==i)
		return i;
	z[i]=comp(z[i]);
	return z[i];
}
void glue(int i, int j)
{
	z[comp(i)]=comp(j);
}
void qs(int i, int j)
{
	int s=i,d=j,piv=h[(i+j)/2],aux;
	while(s<=d)
	{
		while(c[h[s]]<c[piv])
			s++;
		while(c[h[d]]>c[piv])
			d--;
		if(s<=d)
		{
			aux=h[s];
			h[s]=h[d];
			h[d]=aux;
			s++;
			d--;
		}
	}
	if(s<j)
		qs(s,j);
	if(i<d)
		qs(i,d);
}
int main()
{
	int i;
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x[i]>>y[i]>>c[i];
		h[i]=i;
	}
	qs(1,m);
	for(i=1;i<=n;i++)
		z[i]=i;
	for(i=1;i<=m;i++)
		if(comp(x[h[i]])!=comp(y[h[i]]))
		{
			pampam+=c[h[i]];
			glue(x[h[i]],y[h[i]]);
			sol[++k]=h[i];
		}
	g<<pampam<<'\n'<<n-1<<'\n';	
	for(i=1;i<=k;i++)
		g<<x[sol[i]]<<' '<<y[sol[i]]<<'\n';
	return 0;
}