#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

ll n,m,k,d;
vector<vector<ll>> adj;
vector<ll> cau(ll st){
    vector<ll> re(n,0);
    vector<ll> vis(n,0);
    vis[st] = 1;
    queue<pair<ll,ll>> q;
    q.push({st,0});

    while(q.size()){
        auto&[x,dis] = q.front();q.pop();
        re[x] = dis;
        // cout<<x<<" "<<dis<<endl;
        for(auto to:adj[x]){
            if(vis[to]) continue;
            vis[to] = 1;
            q.push({to,dis+1});
        }
    } 
    return re;
}

vector<ll> f;

void init(){
    f = vector<ll> (n,0);
    f[0] = d;
    ll dis = 0;
    for(ll i =1;i<n;i++){
        dis++;
        if(dis==d) dis = 0;
        f[i] = f[i-1]+d-dis;
    }
    // for(ll x:f) cout<<x<<" ";
    // cout<<endl;
}


void solve(){
    cin>>n>>m>>k>>d;
    k--;
    adj = vector<vector<ll>> (n);
    for(ll i=0;i<m;i++){
        ll x,y;cin>>x>>y;x--;y--;
        adj[x].push_back(y);adj[y].push_back(x);
    }
    auto at_dis = cau(k);
    auto over_dis =cau(n-1);
    init();
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
    vector<ll> vis(n,0);vis[0] = 1;
    ll ans = f[over_dis[0]-1];
    for(ll to:adj[0]){
        if(at_dis[to]>=d){
            ans = min(ans,f[over_dis[to]]);
            continue;
        }else{
            pq.push({d-at_dis[to],to});
        }
    }


    while(pq.size()){
        while(pq.size()&&vis[pq.top().second]) pq.pop();
        if(pq.size()==0) break;

        auto p = pq.top();pq.pop();
        ll cost = p.first,x =p.second;
        vis[x] = 1;
        // cout<<"x:"<<x<<" cost:"<<cost<<endl;
        // if(x==8&&cost==4){
        //     while(pq.size()) cout<<pq.top().first<<" "<<pq.top().second<<endl,pq.pop();
        //     return;
        // }
        for(auto to:adj[x]){
            if(at_dis[to]>=d){
                ans = min(ans,cost+f[over_dis[to]]);
                continue;
            }
            if(vis[to]) continue;
            // cout<<"to:"<< to<<" "<<cost+d-at_dis[to]<<endl;
            pq.push({cost+d-at_dis[to],to});
            // vis[to] = 1;
        }
    }

    cout<<ans<<endl;

}

/*
5 5 2 2
1 2
2 4
4 5
1 3
3 5

5 4 1 3 
1 2
2 3
3 4 
4 5
*/

signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    ll t = 1;
    // cin>>t;
    while(t--)
        solve();
}









/*


    vector<ll> dp(n,1e18);
    vector<ll> vis(n,0);
    queue<ll> q;
    q.push(0);vis[0] = 1;dp[0]=0;
    ll ans = f[over_dis[0]];
    while(q.size()){
        ll x = q.front();q.pop();
        if(x!=0&&at_dis[x] >= d){
            ans = min(ans,dp[x]+f[over_dis[x]]);
            continue;
        }
        if(x==n-1){
            ans = min(ans,dp[n-1]);
            continue;
        }
        for(auto to:adj[x]){
            if(vis[to]) continue;
            if(at_dis[to]<d) dp[to] = min(dp[to],dp[x]+d-at_dis[to]);
            else dp[to] = min(dp[to],dp[x]);
            // cout<<x<<" "<<to<<" "<<dp[to]<<endl;
            vis[to] =1;q.push(to);
        }
    }
*/