# include <stdio.h>
# define nmax 801
# define mmax 1501
struct muchie{
	int x,y,ct;
}G[mmax],S[mmax];
int N,M,C[nmax];
void sort(int st,int dr)
{
    int i=st,j=dr;
    muchie p=G[(i+j)/2],tmp;
    do{
	while (G[i].ct<p.ct) ++i;
	while (p.ct<G[j].ct) --j;
	if (i<=j){
	    tmp=G[i], G[i]=G[j],G[j]=tmp;
	    ++i; --j;
	}
    } while (i<=j);
    if (i<dr) sort(i,dr);
    if (st<j) sort(st,j);
}

int main(){
  int i,a,b,k,j;
  long CT=0;
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  scanf("%d %d",&N,&M);
  for (i=1;i<=M;++i)
    scanf("%d %d %d",&G[i].x,&G[i].y,&G[i].ct);
  sort(1,M);
  for (i=1;i<=N;++i) C[i]=i;
  k=1;
  for (i=1;i<N;++i){
      while (C[G[k].x]==C[G[k].y] && k<M) k++;
      CT+=G[k].ct; S[i]=G[k];
      a=G[k].x; b=G[k].y;
      for (j=1;j<=N;j++)
	if (C[j]==C[a]) C[j]=C[b];
  }
  printf("%ld\n",CT);
  printf("%d\n",N-1);
  for (i=1;i<N;++i)
     printf("%d %d\n",S[i].x,S[i].y);
  return 0;
}