#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast", "-funroll-loops", "-fdelete-null-pointer-checks")
#pragma GCC target("ssse3", "sse3", "sse2", "sse", "avx2", "avx")
using namespace std;
const long long inf = 0x7f7f7f7f7f7f;
long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = getchar();
  }
  return x * f;
}
const long long N = 3060;
vector<long long> G[N];
long long n, m;
long long s1, t1, l1;
long long s2, t2, l2;
long long vis[N], dis[N][N];
void bfs(long long s) {
  memset(vis, 0, sizeof(vis));
  queue<long long> q;
  q.push(s);
  dis[s][s] = 0;
  while (q.size() > 0) {
    long long u = q.front();
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (long long v : G[u]) {
      if (dis[s][v] == -1) {
        dis[s][v] = dis[s][u] + 1;
        q.push(v);
      }
    }
  }
}
long long the_min_of_save = inf;
signed main() {
  memset(dis, -1, sizeof(dis));
  n = read(), m = read();
  for (long long i = 1; i <= m; i++) {
    long long u = read(), v = read();
    G[u].push_back(v);
    G[v].push_back(u);
  }
  s1 = read(), t1 = read(), l1 = read();
  s2 = read(), t2 = read(), l2 = read();
  for (long long i = 1; i <= n; i++) bfs(i);
  for (long long i = 1; i <= n; i++) {
    for (long long j = 1; j <= n; j++) {
      if (dis[s1][i] + dis[i][j] + dis[j][t1] > l1) continue;
      if (dis[s2][i] + dis[i][j] + dis[j][t2] > l2) continue;
      the_min_of_save =
          min(the_min_of_save,
              dis[s1][i] + dis[i][j] + dis[j][t1] + dis[s2][i] + dis[j][t2]);
    }
  }
  if (dis[s1][t1] <= l1 && dis[s2][t2] <= l2)
    the_min_of_save = min(the_min_of_save, dis[s1][t1] + dis[s2][t2]);
  swap(s2, t2);
  for (long long i = 1; i <= n; i++) {
    for (long long j = 1; j <= n; j++) {
      if (dis[s1][i] + dis[i][j] + dis[j][t1] > l1) continue;
      if (dis[s2][i] + dis[i][j] + dis[j][t2] > l2) continue;
      the_min_of_save =
          min(the_min_of_save,
              dis[s1][i] + dis[i][j] + dis[j][t1] + dis[s2][i] + dis[j][t2]);
    }
  }
  if (dis[s1][t1] <= l1 && dis[s2][t2] <= l2)
    the_min_of_save = min(the_min_of_save, dis[s1][t1] + dis[s2][t2]);
  if (the_min_of_save > m)
    puts("-1");
  else
    printf("%lld\n", m - the_min_of_save);
}
