#include <bits/stdc++.h>
using namespace std;
struct node {
  int a, b, c, d;
};
bool cmp(const node &first, const node &sec) {
  if (first.a != sec.a) return first.a < sec.a;
  return first.b < sec.b;
}
bool operator<(const node &left, const node &right) { return left.b < right.b; }
int d[3005][3005], c[3005];
vector<int> v[3005];
int bfs(int x) {
  int i, y, z;
  d[x][x] = 0;
  c[x] = x;
  queue<int> q;
  q.push(x);
  while (!q.empty()) {
    y = q.front();
    q.pop();
    for (i = 0; i < v[y].size(); i++) {
      z = v[y][i];
      if (c[z] < x) {
        c[z] = x;
        d[x][z] = d[x][y] + 1;
        q.push(z);
      }
    }
  }
  return 0;
}
int main() {
  int n, m, i, j, ans = 100000, a, b, s1, s2, d1, d2, t1, t2, tim1, tim2;
  cin >> n >> m;
  for (i = 1; i <= m; i++) {
    scanf("%d", &a);
    scanf("%d", &b);
    v[a].push_back(b);
    v[b].push_back(a);
  }
  for (i = 1; i <= n; i++) bfs(i);
  cin >> s1 >> d1 >> t1;
  cin >> s2 >> d2 >> t2;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      tim1 =
          min((d[s1][i] + d[i][j] + d[j][d1]), (d[s1][j] + d[j][i] + d[i][d1]));
      tim2 =
          min((d[s2][i] + d[i][j] + d[j][d2]), (d[s2][j] + d[j][i] + d[i][d2]));
      if ((tim1 <= t1) && (tim2 <= t2)) ans = min(ans, tim1 + tim2 - d[i][j]);
    }
  }
  tim1 = d[s1][d1];
  tim2 = d[s2][d2];
  if ((tim1 <= t1) && (tim2 <= t2)) ans = min(ans, tim1 + tim2 - d[i][j]);
  if (ans > m)
    cout << "-1";
  else
    cout << m - ans;
  return 0;
}
