#include<fstream.h>
long int n,m;
struct muchii{long int x,y,c;}v[400001];

void qsort(long int p,long int q)
{long int st=p,dr=q,a=v[p].x,b=v[p].y,d=v[p].c;
while(st<dr)
	{while(st<dr && d<=v[dr].c)dr--;
	v[st].x=v[dr].x; v[st].y=v[dr].y; v[st].c=v[dr].c;
	while(st<dr && d>=v[st].c)st++;
	v[dr].x=v[st].x; v[dr].y=v[st].y; v[dr].c=v[st].c;
	}
v[st].x=a; v[st].y=b; v[st].c=d;
if(p<st-1) qsort(p,st-1);
if(q>st+1) qsort(st+1,q);
}

int main()
{ifstream f("apm.in");
ofstream g("apm.out");
long int i,a,b,j,viz[400001],comp[400001],cost=0,nr=0;
f>>n>>m;
for(i=1;i<=m;++i)
	f>>v[i].x>>v[i].y>>v[i].c;
for(i=1;i<=m;i++)comp[i]=i;
qsort(1,m);
for(i=1;i<=m && nr<n-1;++i)
	{if(comp[v[i].x]!=comp[v[i].y])
		{nr++;
		cost+=v[i].c;
		viz[i]=1;
		a=comp[v[i].x]; b=comp[v[i].y];
		for(j=1;j<=m;++j)
			if(comp[j]==a) comp[j]=b;
		}
	}
g<<cost<<'\n'<<n-1<<'\n';
for(i=1;i<=m&&nr>0;++i)
	if(viz[i]==1){g<<v[i].x<<' '<<v[i].y<<'\n';nr--;}
f.close();
g.close();
return 0;
}