#include<fstream>
using namespace std;
typedef
struct nod
{
	int nr,cost;
	nod*urm;
}*Pnod;
Pnod l[200005];
int n,m,v[200005],t[200005],h[200005],poz[200005],k,cstot,mch;
const int inf=1<<30;
void citire()
{
	ifstream fin("apm.in");
	fin>>n>>m;
	int i,j,c;
	Pnod p;
	while(fin>>i>>j>>c)
	{
		p=new(nod);
		p->nr=j;
		p->cost=c;
		p->urm=l[i];
		l[i]=p;
		p=new(nod);
		p->nr=i;
		p->cost=c;
		p->urm=l[j];
		l[j]=p;
	}
	fin.close();
}
void sus(int caut)
{
	int var;
	while(caut>1&&(v[h[caut/2]]>v[h[caut]]))
	{
		poz[h[caut/2]]=caut;
		poz[h[caut]]=caut/2;
		var=h[caut];
		h[caut]=h[caut/2];
		h[caut/2]=var;
		caut=caut/2;
	}
}
void jos()
{
	int fiu, caut,var;
	caut=1;
	do
	{
		fiu=0;
		if(caut*2<=k)
		{
			fiu=caut*2;
			if((caut*2)+1<=k&&v[h[caut*2]]>v[h[(caut*2)+1]])
				fiu=(caut*2)+1;
			if(v[h[fiu]]>=v[h[caut]])
				fiu=0;
		}
		if(fiu!=0)
		{
			poz[h[caut]]=fiu;
			poz[h[fiu]]=caut;
			var=h[caut];
			h[caut]=h[fiu];
			h[fiu]=var;
			caut=fiu;
		}
	}while(fiu!=0);
}
void sterge()
{
	h[1]=h[k];
	poz[h[k]]=1;
	k--;
	if(k!=0)
		jos();
}
void prim()
{
	int i,x;
	for(i=2;i<=n;i++)
		v[i]=inf;
	v[1]=0;
	Pnod p;
	for(p=l[1];p!=NULL;p=p->urm)
	{
				v[p->nr]=p->cost;
				t[p->nr]=1;
		
	}
	for(i=2;i<=n;i++)
	{
		h[++k]=i;
		poz[i]=k;
		sus(k);
	}
    for(i=1;i<n;i++)
    {
			x=h[1];
			cstot+=v[x];
			mch++;
			sterge();
			poz[x]=0;
			for(p=l[x];p!=NULL;p=p->urm)
			{
				if(p->cost<v[p->nr]&&poz[p->nr]!=0)
				{
					v[p->nr]=p->cost;
					t[p->nr]=x;
					sus(poz[p->nr]);
				}
			}
	}
}
int main()
{
	citire();
	prim();
	int i;
	ofstream fout("apm.out");
	fout<<cstot<<'\n';
	fout<<mch<<'\n';
	for(i=2;i<=n;i++)
		if(t[i]!=0)
		fout<<t[i]<<" "<<i<<'\n';
	fout.close();
	return 0;
}