#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
vector<long long> dijkstra(long long s,
                           vector<vector<pair<long long, long long>>> &G) {
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      que;
  long long n = G.size();
  vector<long long> dist(n);
  dist.assign(n, (1LL << 60));
  dist[s] = 0;
  que.push(pair<long long, long long>(0, s));
  while (!que.empty()) {
    pair<long long, long long> p = que.top();
    que.pop();
    long long v = p.second;
    for (long long i = (0); i < ((G[v].size())); ++i) {
      if (dist[G[v][i].first] > dist[v] + G[v][i].second) {
        dist[G[v][i].first] = dist[v] + G[v][i].second;
        que.push(
            pair<long long, long long>(dist[G[v][i].first], G[v][i].first));
      }
    }
  }
  return dist;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  vector<vector<pair<long long, long long>>> edge(n);
  for (long long _ = (0); _ < ((m)); ++_) {
    long long x, y;
    cin >> x >> y;
    x--;
    y--;
    edge[x].emplace_back(pair<long long, long long>(y, 1));
    edge[y].emplace_back(pair<long long, long long>(x, 1));
  }
  vector<long long> dist[n];
  for (long long i = (0); i < ((n)); ++i) dist[i] = dijkstra(i, edge);
  long long s, t, c1, u, v, c2;
  cin >> s >> t >> c1 >> u >> v >> c2;
  s--;
  t--;
  u--;
  v--;
  long long mn = (1LL << 60);
  if (dist[s][t] <= c1 && dist[u][v] <= c2) mn = dist[s][t] + dist[u][v];
  for (long long i = (0); i < ((n)); ++i) {
    for (long long j = (0); j < ((n)); ++j) {
      if (dist[s][i] + dist[i][j] + dist[j][t] <= c1 &&
          dist[u][i] + dist[i][j] + dist[j][v] <= c2) {
        mn = min(
            mn, dist[s][i] + dist[i][j] + dist[j][t] + dist[u][i] + dist[j][v]);
      }
      if (dist[s][i] + dist[i][j] + dist[j][t] <= c1 &&
          dist[v][i] + dist[i][j] + dist[j][u] <= c2) {
        mn = min(
            mn, dist[s][i] + dist[i][j] + dist[j][t] + dist[v][i] + dist[j][u]);
      }
    }
  }
  if (mn == (1LL << 60))
    cout << -1 << endl;
  else
    cout << m - mn << endl;
  return 0;
}
