#include <bits/stdc++.h>
using namespace std;
vector<int> v[3005];
int dis[3005][3005];
int vis[3005];
int n, m;
int s1, t1, l1, s2, t2, l2;
void bfs(int start) {
  for (int i = 0; i < 3005; i++) vis[i] = 0;
  dis[start][start] = 0;
  vis[start] = 1;
  queue<int> q;
  q.push(start);
  int now;
  while (!q.empty()) {
    now = q.front();
    q.pop();
    for (int i = 0; i < v[now].size(); i++)
      if (vis[v[now][i]] == 0) {
        dis[start][v[now][i]] = dis[start][now] + 1;
        vis[v[now][i]] = 1;
        q.push(v[now][i]);
      }
  }
}
int main() {
  cin >> n >> m;
  int a, b;
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++) dis[i][j] = 1000000;
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    v[a].push_back(b);
    v[b].push_back(a);
  }
  cin >> s1 >> t1 >> l1;
  cin >> s2 >> t2 >> l2;
  for (int i = 1; i <= n; i++) bfs(i);
  if (dis[s1][t1] > l1 || dis[s2][t2] > l2) {
    cout << -1 << endl;
    return 0;
  }
  int ans = dis[s1][t1] + dis[s2][t2];
  int L1, L2, L3;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      L1 = dis[s1][i] + dis[i][j] + dis[j][t1];
      L2 = dis[s1][j] + dis[j][i] + dis[i][t1];
      L3 = dis[s2][i] + dis[i][j] + dis[j][t2];
      if (L1 <= l1 && L3 <= l2) ans = min(ans, L1 + L3 - dis[i][j]);
      if (L2 <= l1 && L3 <= l2) ans = min(ans, L2 + L3 - dis[i][j]);
    }
  cout << m - ans << endl;
  return 0;
}
