#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;
	for(i=2;i<=n;i++)
	{
		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;
}