#include <bits/stdc++.h>

using i64 = long long;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, m, k, d;
	std::cin >> n >> m >> k >> d;
	k--;
	std::vector<std::vector<int>> adj(n);
	for (int i = 0; i < m; i++) {
		int x, y;
		std::cin >> x >> y;
		x--, y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	i64 inf = 1E12;
	std::vector<int> p(n), dis(n, n);
	std::vector<i64> dp(n,inf);
	p[k] = d;
	std::queue<int> q;
	q.push(k);
	
	while (!q.empty()) {
		auto x = q.front();
		q.pop();

		if (p[x] == 1) {
			continue;
		}

		for (auto y : adj[x]) {
			if (p[y] == 0) {
				p[y] = p[x] - 1;
				q.push(y);
			}
		}
	}

	std::priority_queue<std::pair<i64,int>, std::vector<std::pair<i64, int>>, std::greater<>> h;
	for(auto v : adj[0]){
		if(p[v]!=0){
			dp[v]=p[v];
			h.push({dp[v], v});
		}
	}
	
	while (!q.empty()) q.pop();
	dis[n - 1] = 0;
	q.push(n - 1);
	while (!q.empty()) {
		int x = q.front();
		q.pop();

		for (auto y : adj[x]) {
			if (dis[y] > dis[x] + 1) {
				dis[y] = dis[x] + 1;
				q.push(y);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		dis[i]++;
	}
	i64 ans = inf;
	ans = std::min(ans, dp[n - 1]);

	auto cal = [&](int x) {
		i64 time = 1LL * x / d * (1 + d) * d / 2; 
		x %= d;
		if (x > 0) {
			time += 1LL * (2 * d - x + 1) * x / 2;
		}
		return time;
	};
	while (!h.empty()) {
		auto [val, x] = h.top();
		h.pop();

		// std::cout << x << " " << val << "\n";
		if (val > dp[x]) {
			continue;
		}	

		for (auto y : adj[x]) {
			if (p[y] == 0) {
				ans = std::min(ans, val + cal(dis[y]));
				// std::cout << x << " " << val << " " << cal(dis[x]) << "\n";
			} else if (dp[y] > dp[x] + p[y]) {
				dp[y] = dp[x] + p[y];
				h.emplace(dp[y], y);
			}
		}
	}
	for(auto v:adj[0]) {
		if (p[v] == 0) {
			ans = std::min(ans, cal(dis[v]));
		}
	}
	std::cout << ans << "\n";

	return 0;
}