#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
const int maxn=2e5+10;
void qmax(int &x,int y) { x=max(x,y); }
void qmin(int &x,int y) { x=min(x,y); }
int n,k,d,m,inf=2e18;
int a[maxn];
vector <int> ver[maxn];
int distk[maxn],visk[maxn],distn[maxn],visn[maxn];
int cost[maxn];
int dist1[maxn],vis1[maxn];
struct node1
{
	int num,val;
	bool operator < (const node1 &tp) //不加.val的就是第一个
	const {
		return val>tp.val;
	}
};
void solve(){
	cin>>n>>m>>k>>d;
	cost[0]=0; int cur=d;
	for(int i=1;i<=n;i++){
		cost[i]=cost[i-1]+cur;
		cur--; if(cur==0) cur=d;
	}
	for(int i=1;i<=m;i++){
		int u,v; cin>>u>>v;
		ver[u].push_back(v);
		ver[v].push_back(u);
	}
	memset(distk,0x3f,sizeof(distk)); memset(distn,0x3f,sizeof(distn));
	queue <int> q;
	distk[k]=0; q.push(k);
	while(q.size()){
		int tx=q.front(); q.pop();
		if(visk[tx]) continue;
		visk[tx]=1;
		for(auto u:ver[tx]){
			if(distk[tx]+1<distk[u]){
				distk[u]=distk[tx]+1;
				q.push(u);
			}
		}
	}
	distn[n]=1; q.push(n);
	while(q.size()){
		int tx=q.front(); q.pop();
		if(visn[tx]) continue;
		visn[tx]=1;
		for(auto u:ver[tx]){
			if(distn[tx]+1<distn[u]){
				distn[u]=distn[tx]+1;
				q.push(u);
			}
		}
	}
	int ans=inf;
	for(auto u:ver[1]){
		if(distk[u]>=d){
			qmin(ans,cost[distn[u]]);
		}
	}
	if(distk[1]>d){
		cout<<ans<<"\n";
		return;
	}
	//cout<<ans<<"\n";
	priority_queue <node1> Q;
	memset(dist1,0x3f,sizeof(dist1));
	dist1[1]=0;
	Q.push({1,0});
	while(!Q.empty())
	{
		int x=Q.top().num;
		Q.pop();
		if(vis1[x]) continue;
		vis1[x]=1;
		if(distk[x]>=d&&x!=1) continue;
		for(auto u:ver[x])
		{
			if(dist1[x]+d-distk[u]<dist1[u])
			{
				dist1[u]=dist1[x]+d-distk[u];
				if(distk[u]<d) Q.push({u,dist1[u]});
			}
		}
	}
	//cout<<dist1[6]<<endl;;
	if(dist1[n]<d){
		qmin(ans,dist1[n]);
	}
	for(int i=2;i<=n;i++){
		if(distk[i]==d){
			//cout<<i<<" "<<dist1[i]<<" "<<cost[distn[i]]<<endl;
			qmin(ans,dist1[i]+cost[distn[i]]);
		}
	}
	cout<<ans<<"\n";
}
signed main(){
    ios::sync_with_stdio(0);
	int t;
	t=1;
    while(t--) solve();
    return 0;
}