#include <stdio.h>
#include <limits.h>

#define Nadejde 7
#define Smerenie 3
#define NIL 0

#define ll long long

typedef struct {
  int l, c, time, next;
} portal;

int N, M, T;
ll int min;
portal l[Nadejde + 1];
char seen[Nadejde + 1];

/** abs(X). **/
ll int ABS(int X) {
  return X > 0 ? X : -X;
}

/** Adauga portalul de pe pozitia (l, c). **/
void addPortal(int l0, int c0, int time, int pos, int next) {
  l[pos].l = l0;
  l[pos].c = c0;
  l[pos].time = time;
  l[pos].next = next;
}

/** Seteaza valorile in "seen". **/
void set(int p, int val) {
  seen[p] = seen[l[p].next] = val;
}

/** Genereaza toate combinarile de intrare in portaluri. **/
void bkt(int curr, ll int d) {
  /* Daca am ajuns la destinatie. */
  if (curr == Nadejde) {
    if (d < min) {
      min = d;
    }
  } else {
    int p;
    /* Probam urmatoarele portaluri. */
    for (p = 1; p <= Nadejde; p++) {
      if (!seen[p]) {
        set(p, !NIL);
        bkt(l[p].next, d + l[p].time + ABS(l[curr].l - l[p].l) + ABS(l[curr].c - l[p].c));
        set(p, NIL);
      }
    }
  }
}

/** Raspunde la un test. */
ll int query(FILE *f) {
  int i, l, c, l0, c0, time;
  min = LLONG_MAX;

  /* Citeste datele de intrare. */
  fscanf(f, "%d %d", &N, &M);
  for (i = 1; i <= Smerenie; i++) {
    fscanf(f, "%d %d %d %d %d", &l, &c, &l0, &c0, &time);
    addPortal(l, c, time, i, i + Smerenie);
    addPortal(l0, c0, time, i + Smerenie, i);
  }
  addPortal(N, M, 0, Nadejde, Nadejde);

  /* Gaseste timpul minim. */
  seen[NIL] = !NIL;
  bkt(NIL, NIL);
  seen[!NIL] = NIL;
  return min;
}

int main(void) {
  FILE *in = fopen("portal3.in", "r");
  FILE *out = fopen("portal3.out", "w");

  /* Citeste testele. */
  fscanf(in, "%d", &T);
  while (T--) {
    fprintf(out, "%lld\n", query(in));
  }
  fclose(in);
  fclose(out);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}