#include <stdio.h>
#include <stdlib.h>
#define w(n,t) (t*)malloc((n)*sizeof(t))
#define fr(i,a,b) for(i=a;i<b;++i)
int*o,*O,*c,*I,*p,*P;
int g(int i){
int j=i;
while(j!=p[j])j=p[j];
return p[i]=j;
}
void G(int i,int j){
if(P[i]<P[j])i^=j^=i^=j;
p[j]=i;
P[i]+=P[i]==P[j];
}
int cmp(const void*a,const void*b){return c[*(int*)a]-c[*(int*)b];}
int main(){
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
int n,m,i;
scanf("%i%i",&n,&m);
printf("n=%i m=%i\n",n,m);
o=w(m,int);O=w(m,int);c=w(m,int);I=w(m,int);
fr(i,0,m)scanf("%i%i%i",o+i,O+i,c+i),I[i]=i,--O[i]-o[i]--;
qsort(I,m,sizeof(*I),cmp);
p=w(n,int);P=w(n,int);
fr(i,0,n)p[i]=i,P[i]=1;
int s=0,j;
int*x=w(n-1,int),*X=w(n-1,int),y=0;
fr(i,0,m){
int a=o[I[i]],b=O[I[i]];
int A=g(a),B=g(b);
if(A==B)continue;
x[y]=a,X[y++]=b;
s+=c[I[i]];
G(A,B);
}
printf("%i\n",s);
printf("%i\n",y);
fr(i,0,y)printf("%i %i\n",x[i]+1,X[i]+1);
return 0;
}