#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
long long inf=1e16;
long long dist[200005];
long long dist2[200005];
long long dist3[200005];
long long lung[200005];
vector<long long>adj[200005];
queue<long long>qu;
priority_queue<pair<long long,long long> >pq;
int main()
{
    long long n,i,j,k,l,op,t,a,b,sum=0,m,st,r;
    cin>>n>>m>>st>>r;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(i=1;i<=n;i++)
    {
        dist[i]=0;
    }
    dist[st]=r;
    qu.push(st);
    while(qu.size())
    {
        long long curr=qu.front();
        qu.pop();
        for(auto k:adj[curr])
        {
            if(dist[k]<dist[curr]-1)
            {
                dist[k]=dist[curr]-1;
                qu.push(k);
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        dist2[i]=inf;
    }
    dist2[1]=0;
    pq.push({0,1});
    while(pq.size())
    {
        long long curr=pq.top().second;
        long long val=pq.top().first;
        pq.pop();
        if(val==-dist2[curr] && (dist[curr]>=1 || curr==1))
        {
            for(auto k:adj[curr])
            {
                if(dist2[curr]+dist[k]<dist2[k])
                {
                    dist2[k]=dist2[curr]+dist[k];
                    pq.push({-dist2[k],k});
                }
            }
        }
    }
    long long val=r;
    for(i=1;i<=n;i++)
    {
        lung[i]=lung[i-1]+val;
        val--;
        if(val==0)
        {
            val=r;
        }
    }
    for(i=1;i<=n;i++)
    {
        dist3[i]=inf;
    }
    dist3[n]=0;
    qu.push(n);
    while(qu.size())
    {
        long long curr=qu.front();
        qu.pop();
        for(auto k:adj[curr])
        {
            if(dist3[k]>dist3[curr]+1)
            {
                dist3[k]=dist3[curr]+1;
                qu.push(k);
            }
        }
    }
    long long sol=dist2[n];
    for(i=1;i<=n;i++)
    {
        cout<<i<<"  "<<dist[i]<<" "<<dist2[i]<<" "<<dist3[i]<<'\n';
    }
    for(i=2;i<=n;i++)
    {
        if(dist[i]==0)
        {
            sol=min(sol,dist2[i]+lung[dist3[i]+1]);
        }
    }
    cout<<sol;
    return 0;
}