#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long 

const int N=200010;
int n,m,K,D,inf,dis[2][N];

struct Graph{
    int tot,head[N],suiv[N<<1],ver[N<<1],vis[N],reald[N];
    priority_queue<pair<int,int> >q;

    inline void lnk(int x,int y)
    {
        ver[++tot]=y;
        suiv[tot]=head[x];
        head[x]=tot;
    }

    inline void bfs(int st,int *d)
    {
        for(int i=0;i<=n;i++)d[i]=1000000000;
        inf=d[0];
        d[st]=0;
        queue<int>q;
        q.push(st);
        while(q.size())
        {
            int x=q.front();q.pop();
            for(int i=head[x];i;i=suiv[i])
            {
                int y=ver[i];
                if(d[y]!=inf)continue;
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }

    inline void dijkstra(int st)
    {
        memset(reald,0x3f,sizeof(reald));
        reald[st]=0;
        q.push(make_pair(0,st));
        while(q.size())
        {
            int x=q.top().second;q.pop();
            if(vis[x])continue;
            vis[x]=1;
            //    cout<<"x "<<x<<endl;
            for(int i=head[x];i;i=suiv[i])
            {
                int y=ver[i],z=(D-dis[1][y])?D-dis[1][y]:D;
                if(dis[1][y]>D)continue;
                //   cout<<"y "<<y<<" "<<z<<endl;;
                if(reald[y]>reald[x]+z)
                {

                    reald[y]=reald[x]+z;
                    //      cout<<"reald "<<y<<" "<<reald[y]<<endl;
                    q.push(make_pair(-reald[y],y));
                }
            }
        }
    }

}e;

inline int cal(int t) // d-1 + d-2 + d-3 .... 1 + d + d-1 + d-2 .... t terms totally
{
    if(t<=D-1)
        return (D-1+D-1-t+1)*t/2;
    int tem=t-(t)/D*D;
    int lstdis=(t)/D*((1+D)*D)/2+(D-1+D-1-tem+1)*tem/2;
    return lstdis;
}

signed main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&K,&D);
    for(int i=1,x,y;i<=m;i++)
        scanf("%lld%lld",&x,&y),e.lnk(x,y),e.lnk(y,x);
    e.bfs(n,dis[0]);
    e.bfs(K,dis[1]);

    if(dis[1][1]>D)
    {
        int tem=dis[0][1]-(dis[0][1])/D*D;
        int lstdis=(dis[0][1])/D*((1+D)*D)/2+(D+D-tem+1)*tem/2;
        printf("%lld\n",lstdis);
        return 0;
    }

    e.dijkstra(1);
    int ans=1ll<<60;
    for(int i=1;i<=n;i++)
    {
        if(dis[1][i]>=D)
        {
            //    cout<<"i"<<" "<<i<<endl;
            int lstdis=cal(dis[0][i]);
            //    cout<<lstdis<<endl;
            ans=min(ans,lstdis+e.reald[i]);
        }
    }
    if(ans==1ll<<60)ans=e.reald[n];
    printf("%lld\n",min(ans,e.reald[n]));
    return 0;
}