#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int SIZE = 1e6 + 10;
vector<vector<int> > g;
int dist[3000][3000] = {0};
int main() {
  int n;
  cin >> n;
  int m;
  cin >> m;
  g.resize(n);
  for (int i = 0; i < (m); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  int s1, t1, l1, s2, t2, l2;
  cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2;
  s1--;
  t1--;
  s2--;
  t2--;
  vector<vector<int> > d(n);
  for (int i = 0; i < (n); ++i) {
    vector<int> p(n);
    d[i].assign(n, MOD);
    d[i][i] = 0;
    set<pair<int, int> > q;
    q.insert(make_pair(d[i][i], i));
    while (!q.empty()) {
      int v = q.begin()->second;
      q.erase(q.begin());
      for (size_t j = 0; j < g[v].size(); ++j) {
        int to = g[v][j], len = 1;
        if (d[i][v] + len < d[i][to]) {
          q.erase(make_pair(d[i][to], to));
          d[i][to] = d[i][v] + len;
          p[to] = v;
          q.insert(make_pair(d[i][to], to));
        }
      }
    }
  }
  int ans = -1;
  if ((d[s1][t1] <= l1) && (d[s2][t2] <= l2)) ans = m - (d[s1][t1] + d[s2][t2]);
  for (int i = 0; i < (n); ++i)
    for (int u = 0; u < (n); ++u) {
      if ((d[i][u] + min(d[i][s1], d[u][s1]) + min(d[i][t1], d[u][t1]) <= l1) &&
          (d[i][u] + min(d[i][s2], d[u][s2]) + min(d[i][t2], d[u][t2]) <= l2))
        ans = max(ans, m - d[i][u] - min(d[i][s1], d[u][s1]) -
                           min(d[i][s2], d[u][s2]) - min(d[i][t1], d[u][t1]) -
                           min(d[i][t2], d[u][t2]));
    }
  cout << ans;
  return 0;
}
