#include<fstream.h>  
#include<stdlib.h>  
long int n,m;  
struct muchii{long int x,y;  
	int 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,j,cost=0,* comp;
int viz[400001];

f>>n>>m;
comp=(long *)calloc(m+1,sizeof(long));

for(i=1;i<=m;++i)
   {f>>v[i].x>>v[i].y>>v[i].c; comp[i]=i;}
comp[0]=0;


qsort(1,m);
for(i=1;i<=m && comp[0]<n-1;++i)
    {if(comp[v[i].x]!=comp[v[i].y])
	{comp[0]++;
	cost+=v[i].c;
	viz[i]=1;
	a=comp[v[i].x];
	for(j=1;j<=m;++j)
	    if(comp[j]==a) comp[j]=comp[v[i].y];
	}
    }
g<<cost<<'\n'<<n-1<<'\n';
for(i=1;i<=m;++i)
    if(viz[i]==1)g<<v[i].x<<' '<<v[i].y<<'\n';
f.close();
g.close();
return 0;
}