#include <bits/stdc++.h>
using namespace std;
template <class T>
T mod_f(T num) {
  if (num >= 0)
    return num % 1000000007;
  else
    return ((num % 1000000007) + 1000000007) % 1000000007;
}
template <class T>
T fast_pow(T b, T p) {
  if (p == 0) return 1;
  if (p % 2) {
    T x = mod_f(mod_f(b) * mod_f(fast_pow(b, p - 1)));
    return x;
  } else {
    T x = mod_f(fast_pow(b, p / 2));
    x = mod_f(mod_f(x) * mod_f(x));
    return x;
  }
}
template <class T>
T gcd(T a, T b) {
  a = abs(a);
  b = abs(b);
  while (b) {
    T r = a % b;
    a = b;
    b = r;
  }
  return a;
}
int node, edge, i, u, v;
vector<int> g[3001];
queue<int> Q;
int d[3001][3001], dist[3001];
void bfs(int source) {
  memset(dist, -1, sizeof(dist));
  dist[source] = 0;
  Q.push(source);
  while (Q.size()) {
    u = Q.front();
    Q.pop();
    for (int i = 0; i < g[u].size(); i++) {
      v = g[u][i];
      if (dist[v] == -1) {
        dist[v] = dist[u] + 1;
        Q.push(v);
      }
    }
  }
  for (int i = 1; i <= node; i++) d[source][i] = dist[i];
}
int main() {
  ios_base::sync_with_stdio(0);
  int u1, v1, t1, u2, t2, v2, l, r, d1, d2;
  int ans;
  cin >> node >> edge;
  for (i = 1; i <= edge; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  cin >> u1 >> v1 >> t1 >> u2 >> v2 >> t2;
  for (i = 1; i <= node; i++) bfs(i);
  if (d[u1][v1] <= t1 and d[u2][v2] <= t2)
    ans = edge - d[u1][v1] - d[u2][v2];
  else
    ans = -1;
  for (l = 1; l <= node; l++) {
    for (r = 1; r <= node; r++) {
      d1 = d[u1][l] + d[l][r] + d[r][v1];
      d2 = d[u2][l] + d[l][r] + d[r][v2];
      d1 = min(d1, d[v1][l] + d[l][r] + d[r][u1]);
      d2 = min(d2, d[v2][l] + d[l][r] + d[r][u2]);
      if (d1 <= t1 and d2 <= t2) ans = max(ans, edge - d1 - d2 + d[l][r]);
    }
  }
  cout << ans << endl;
  return 0;
}
