#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 1, INF = 0x3f3f3f3f;
vector<int> adj[MAXN];
long long DIST[MAXN], BEST[MAXN];
long long DISTN[MAXN];
int N, M, K, D;

void bfs() {
  queue<pair<int, int>> q; 
  q.push({0, K});
  DIST[K] = 0;
  while (!q.empty()) {
    auto node = q.front(); q.pop();
    if (DIST[node.second] < node.first) continue;
    for (auto it : adj[node.second]) {
      if (DIST[it] < node.first + 1) continue;
      q.push({node.first + 1, it});
      DIST[it] = node.first + 1;
    }
  }
  /*
  q.push({0, N});
  DISTN[N] = 0;
  while (!q.empty()) {
    auto node = q.front(); q.pop();
    if (DISTN[node.second] < node.first) continue;
    for (auto it : adj[node.second]) {
      if (DISTN[it] < node.first + 1) continue;
      q.push({node.first + 1, it});
      DISTN[it] = node.first + 1;
    }
  }
  */
}

long long range(long long n) {
  if (n < 1) return 0;
  return (n * (n + 1)) >> 1;
}

long long range(int l, int r) {
  return range(r) - range(l - 1);
}

long long calc(int node) {
  long long ret = 0;
  long long full = (DISTN[node] + 1) / D;
  ret += full * range(1, D);
  if ((DISTN[node] + 1) % D)
  ret += range(D - DISTN[node] % D, D);
  return ret;
}

long long dijkstra(int st) {
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  pq.push({0, st});
  BEST[st] = 0;
  long long ans = 0;
  while (!pq.empty()) {
    auto [cost, node] = pq.top(); pq.pop(); 
    assert(cost >= 0);
    if (node == N) return cost;
    if (BEST[node] < cost) continue;
    for (auto it : adj[node]) {
      if (DIST[it] >= D) {
        if (BEST[N] > cost + calc(it)) {
          BEST[N] = cost + calc(it);
          pq.push({cost + calc(it), N});
        }
      }
      else if (BEST[it] > cost + D - DIST[it]) {
        BEST[it] = cost + D - DIST[it];
        pq.push({cost + D - DIST[it], it});
      }
    }
  }
  return -1;
}


int main() {
  cin.tie(0)->sync_with_stdio(false);
  memset(DIST, INF, sizeof DIST);
  memset(DISTN, INF, sizeof DISTN);
  memset(BEST, INF, sizeof BEST);
  cerr << DIST[0] << endl;
  cin >> N >> M >> K >> D;
  for (int i = 0; i < M; ++i) {
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  bfs();
  cout << dijkstra(1);
  return 0;
}