#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define fi first
#define se second
#define all(_a) _a.begin(), _a.end()
const int N=200010;
vector<int>g[N];
int dist[N],ki[N],s[N],dst[N];
bool st[N];
int n,m,k,d;
int res=INF;
void dijdist(int start){
    for(int i=1;i<=n;i++){
        dist[i]=INF;
        st[i]=false;
    }
    dist[start]=0;
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({0,start});
    while(q.size()){
        int u=q.top().se;
        q.pop();
        if(st[u])continue;
        st[u]=true;
        for(auto v:g[u]){
            if(dist[v]>dist[u]+1){
                dist[v]=dist[u]+1;
                q.push({dist[v],v});
            }
        }
    }
}
void dijki(int start){
    for(int i=1;i<=n;i++){
        ki[i]=INF;
        st[i]=false;
    }
    ki[start]=0;
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({0,start});
    while(q.size()){
        int u=q.top().se;
        q.pop();
        if(st[u])continue;
        st[u]=true;
        for(auto v:g[u]){
            if(ki[v]>ki[u]+1){
                ki[v]=ki[u]+1;
                q.push({ki[v],v});
            }
        }
    }
}
void dij(){
    for(int i=1;i<=n;i++){
        dst[i]=INF;
        st[i]=false;
    }
    dst[1]=0;
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({0,1});
    while(q.size()){
        int u=q.top().se;
        q.pop();
        if(st[u])continue;
        st[u]=true;
        for(auto v:g[u]){
            if(ki[v]>=d){
                res=min(res,s[dist[v]]+dst[u]);
            }else{
                if(dst[v]>dst[u]+d-ki[v]){
                    dst[v]=dst[u]+d-ki[v];
                    q.push({dst[v],v});
                }
            }
        }
    }
}
void solve(){
    cin>>n>>m>>k>>d;
    s[0]=d;
    for(int i=1;i<=m;i++){
        s[i]=s[i-1]+(d-(i%d));
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dijdist(n);
    dijki(k);
    dij();
    res=min(res,dst[n]);
    cout<<res<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << setiosflags(ios::fixed) << setprecision(15);
    int T;
    T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}