#include <cstdio>
#include <cstdlib>

#define MAXN 200000

int X[MAXN+10], Y[MAXN+10], C[MAXN+10];
int T[MAXN+10], next[MAXN+10], RG[MAXN+10], RES[MAXN+10];

int cmp(const void *a, const void *b){
  return (C[*(int*)a] - C[*(int*)b]);
}

int find(int a){
  
  int R, aux;
  for(R=a; T[R]!=R; R=T[R])
    ;
  
  while(T[a]!=a){
    aux=T[a];
    T[a]=R;
    a=aux;
    }

  return R;

}

void comb(int a, int b){

  if(RG[a]>RG[b])
    T[b]=a;
  else
    T[a]=b;
  
  if(RG[a]==RG[b])
    RG[b]++;
}

int main(){

  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);

  int N, M, i, qpos = 0, val = 0;

  scanf("%d%d", &N, &M);
  for(i=1; i<=M; i++){
    scanf("%d%d%d", X+i, Y+i, C+i);
    next[i]=i;
    T[i]=i;
    RG[i]=1;
  }

  qsort(next+1, M, sizeof(int), cmp);

  for(i=1; i<=M; i++){
    if(find(X[next[i]]) != find(Y[next[i]])){
      val+=C[next[i]];
      comb(find(X[next[i]]), find(Y[next[i]]));
      RES[qpos++]=next[i];
    }
  }

  printf("%d\n%d\n", val, N-1);
  for(i=0; i<N-1; i++){
    printf("%d %d\n", X[RES[i]], Y[RES[i]]);
  }

  return 0;
}