# include <stdio.h>   
# define nmax 200001   
# define mmax 400001   
struct muchie{   
    int x,y,ct;   
}G[mmax],S[mmax];   
int N,M,C[nmax],X[nmax],Y[nmax];   
long CT;   
void sort(int st,int dr)   
{   
  int i=st,j=dr;   
  muchie p=G[(st+dr)>>1],aux;   
  if (dr<=st) return;   
  while (i<=j){   
    while (G[i].ct<p.ct) i++;   
    while (p.ct<G[j].ct) j--;   
    if (i<=j) {   
    aux=G[i];G[i]=G[j]; G[j]=aux;   
    i++; j--;   
    }   
  }   
  if (st<j) sort(st,j);   
  if (i<dr) sort(i,dr);}   
int main(){   
  int i,a,k=0,j;   
  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;   
  for (i=1;i<=M && k<N-1;++i){   
    if (C[G[i].x]!=C[G[i].y]){   
    k++;   
    CT+=G[i].ct; X[k]=G[i].x;Y[k]=G[i].y;   
    a=C[G[i].x];   
    for (j=1;j<=N;++j)   
      if (C[j]==a) C[j]=C[G[i].y];   
      }   
   }   
  printf("%ld\n",CT);   
  printf("%d\n",N-1);   
  for (i=1;i<=k;++i)   
     printf("%d %d\n",X[i],Y[i]);   
  return 0;   
}