#include <bits/stdc++.h>
using namespace std;
inline bool isPowerOfTwo(int x) { return (x != 0 && (x & (x - 1)) == 0); }
double pi = 3.141592653589793238462643;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
inline int add(int a, int b, int m = 1000000007) {
  a += b;
  if (a >= m) a -= m;
  return a;
}
inline int mul(int a, int b, int m = 1000000007) {
  return (int)(((long long)a * (long long)b) % m);
}
inline bool ispalin(string &str) {
  int n = str.length();
  for (int i = 0; i < n / 2; i++)
    if (str[i] != str[n - i - 1]) return false;
  return true;
}
long long expo(long long base, long long pow) {
  long long ans = 1;
  while (pow != 0) {
    if (pow & 1 == 1) {
      ans = ans * base;
      ans = ans % 1000000007;
    }
    base *= base;
    base %= 1000000007;
    pow /= 2;
  }
  return ans;
}
void swapp(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}
long long inv(long long x) { return expo(x, 1000000007 - 2); }
int expFactor(int n, int p) {
  int x = p;
  int exponent = 0;
  while ((n / x) > 0) {
    exponent += n / x;
    x *= p;
  }
  return exponent;
}
inline int countsetbit(int n) {
  unsigned int count = 0;
  while (n) {
    n &= (n - 1);
    count++;
  }
  return count;
}
inline int abs(int x) {
  if (x < 0) return -x;
  return x;
}
bool isPal(string ss) {
  int len = ss.length();
  for (int i = 0; i < len / 2; i++) {
    int comp = len - i - 1;
    if (ss[i] != ss[comp]) return false;
  }
  return true;
}
long long _sieve_size;
bitset<10000010> bs;
vector<int> primes;
void sieve(long long upperbound) {
  _sieve_size = upperbound + 1;
  bs.set();
  bs[0] = bs[1] = 0;
  for (long long i = 2; i <= _sieve_size; i++)
    if (bs[i]) {
      for (long long j = i * i; j <= _sieve_size; j += i) bs[j] = 0;
      primes.push_back((int)i);
    }
}
bool isPrime(long long N) {
  if (N <= _sieve_size) return bs[N];
  for (int i = 0; i < (int)primes.size(); i++)
    if (N % primes[i] == 0) return false;
  return true;
}
int d[5005][5005];
vector<int> g[5005];
int main() {
  memset(d, -1, sizeof(d));
  int n, m;
  cin >> n >> m;
  for (int i = (0); i <= (m - 1); ++i) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for (int i = (0); i <= (n - 1); ++i) {
    queue<int> q;
    q.push(i);
    d[i][i] = 0;
    while (!q.empty()) {
      int s = q.front();
      q.pop();
      for (int j = (0); j <= ((int)(g[s].size()) - 1); ++j) {
        int to = g[s][j];
        if (d[i][to] == -1) {
          d[i][to] = d[i][s] + 1;
          q.push(to);
        }
      }
    }
  }
  int s[2], t[2], l[2];
  cin >> s[0] >> t[0] >> l[0];
  s[0]--;
  t[0]--;
  cin >> s[1] >> t[1] >> l[1];
  s[1]--;
  t[1]--;
  int ans = m + 1;
  for (int it = (0); it <= (1); ++it) {
    swap(s[0], t[0]);
    for (int i = (0); i <= (n - 1); ++i) {
      for (int j = (0); j <= (n - 1); ++j) {
        int v[] = {d[s[0]][i] + d[i][j] + d[j][t[0]],
                   d[s[1]][i] + d[i][j] + d[j][t[1]]};
        if (v[0] <= l[0] && v[1] <= l[1]) {
          ans = min(ans, v[0] + v[1] - d[i][j]);
        }
      }
    }
  }
  if (d[s[0]][t[0]] <= l[0] && d[s[1]][t[1]] <= l[1]) {
    ans = min(ans, d[s[0]][t[0]] + d[s[1]][t[1]]);
  }
  if (ans > m) {
    ans = -1;
  } else {
    ans = m - ans;
  }
  cout << ans << endl;
}
