#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int INF=1e18;
void solve() {
  int n,m,k,d;cin>>n>>m>>k>>d;
  vector<vector<int>>pth(n+1);
  vector<int>disn(n+1),disk(n+1),nu(n+1),dis1(n+1);
  for(int i=1;i<=m;i++){
    int u,v;cin>>u>>v;
    pth[u].push_back(v);
    pth[v].push_back(u);
  }
  auto bfs=[&](int pos,vector<int>&di){
    queue<int>q;
    q.push(pos);fill(di.begin(),di.end(),INF);
    di[pos]=0;
    while(!q.empty()){
        int po=q.front();q.pop();
        for(auto &i:pth[po]){
            if(di[i]==INF){
                di[i]=di[po]+1;
                q.push(i);
            }
        }
    }
  };
    bfs(n,disn);
    bfs(k,disk);
    nu[0]=d;
    for(int i=1;i<=n;i++){
        nu[i]=nu[i-1]+(d-i%d);
    }
    int ans=INF;
    priority_queue<pair<int,int>>q;
    q.push({0,1});fill(dis1.begin(),dis1.end(),INF);
    dis1[1]=0;
    while(!q.empty()){
        int di=q.top().first,pos=q.top().second;q.pop();
        if(di>dis1[pos])continue;
        for(auto &i:pth[pos]){
            int len=disk[i];
            if(len>=d){
                ans=min(ans,dis1[pos]+nu[disn[i]]);
            }else{
                if(dis1[i]>dis1[pos]+d-len){
                    dis1[i]=dis1[pos]+d-len;
                    q.push({dis1[i],i});
                }
            }
        }
    }
    cout<<ans<<endl;


}

signed main() {
#ifdef DEBUG
    freopen("demo.in", "r", stdin);
    freopen("demo.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
   
        solve();
    
    return 0;
}