#include <bits/stdc++.h>
const int mod = (int)1e9 + 7;
const int inf = 1e7 + 100;
using namespace std;
template <class T>
void smin(T& a, T val) {
  if (a > val) a = val;
}
template <class T>
void smax(T& a, T val) {
  if (a < val) a = val;
}
const int N = 3000 + 10;
int n, m;
vector<int> v[N];
int dis[N][N];
void bfs(int s, int n) {
  queue<int> q;
  q.push(s);
  for (int i = 1; i <= n; ++i) dis[s][i] = inf;
  dis[s][s] = 0;
  vector<bool> vis(n + 1);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    if (vis[x]) continue;
    vis[x] = 1;
    for (auto it : v[x]) {
      if (dis[s][it] > 1 + dis[s][x]) {
        dis[s][it] = 1 + dis[s][x];
        q.push(it);
      }
    }
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int x, y;
    cin >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  int s1, s2, t1, t2, l1, l2;
  cin >> s1 >> t1 >> l1;
  cin >> s2 >> t2 >> l2;
  int ans = -1;
  for (int i = 1; i <= n; ++i) {
    bfs(i, n);
  }
  if (dis[s1][t1] <= l1 and dis[s2][t2] <= l2) {
    smax(ans, m - (dis[s1][t1] + dis[s2][t2]));
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      int ans1 = dis[s1][i] + dis[i][j] + dis[j][t1];
      int ans2 = dis[s2][i] + dis[i][j] + dis[j][t2];
      if (ans1 <= l1 and ans2 <= l2) {
        smax(ans, m - (ans1 + ans2 - dis[i][j]));
      }
      ans1 = dis[s1][i] + dis[i][j] + dis[j][t1];
      ans2 = dis[s2][j] + dis[j][i] + dis[i][t2];
      if (ans1 <= l1 and ans2 <= l2) {
        smax(ans, m - (ans1 + ans2 - dis[j][i]));
      }
    }
  }
  cout << ans;
  return 0;
}
