#include <bits/stdc++.h>
// #pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
typedef long double db;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
typedef pair<ll, ll> pll;
void init();
#define Clear(a) memset(a, 0, sizeof(a))
#define pb(x) push_back(x)

#define INF 1e9 + 10
const int N = 2e5 + 10;
const int M = 3e4+10;
const ll mod = 1e9+7;
const int B = 233;
const bool IN_TEST = 0;

ll n, m, k, d;
ll dis[N], res[N], ans, dn[N], dk[N], vis[N];
vector<int> from[N];
ll get(ll l,ll r){
	if(l>r){
		return 0;
	}
	return (l+r)*(r-l+1)/2; 
}
ll getsum(ll x){
	return x/d*get(1,d)+get(d+1-x%d,d);
}

struct node {
    ll y, w;
    bool operator<(const node &o) const { return w > o.w; }
};

void dij(ll s, bool flag, ll *dist) {
    for (int i=0;i<=n;i++) dist[i] = 1e18;
    for (int i=0;i<=n;i++) vis[i] = 0;
    priority_queue<node> pq;
    dist[s] = 0;
    pq.push({s, 0});
    auto f = [](ll l,ll r) -> ll {return l > r ? 0ll : (l + r) * (r - l + 1ll) / 2ll;};

    while (pq.size()) {
        auto& now = pq.top();
        pq.pop();
        ll x = now.y, w = now.w;

        if (vis[x]) continue;
        vis[x] = true;

        for (auto y : from[x]) {
            if (!flag) {
                if (dist[x] + 1 < dist[y]) {
                    dist[y] = dist[x] + 1;
                    pq.push({y, dist[y]});
                }
            } else {
                if (dk[y] >= d) {
                    // ll ndis = (dn[y] + 1) / d *f(1, d) + f(d+1 - (dn[y] + 1) % d, d);
                    ans = min(ans, res[x ]+ getsum(dn[y]+1));
                } else if (res[x] + d - dk[y] < res[y]) {
                    res[y] = res[x] + d - dk[y];
                    pq.push({y, res[y]});
                }
            }
        }
    }
}

void solve() {
    cin>>n>>m>>k>>d;
    ans = 1e18;
    for (int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        from[u].pb(v);
        from[v].pb(u);
    }
    dij(k,0,dk);
    dij(n,0,dn);
    dij(1,1,res);
    cout<<min(ans, res[n])<<endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    int t = 1;
    if (IN_TEST)
        cin >> t;
    while (t--)
        solve();
    return 0;
}

void init()
{
}