#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,m,k,d;
int _u[200005],_v[200005];

int cnt;
int head[100005];
struct eg{
	int to,nxt,w;
}edge[500005];

void make(int u,int v,int w){
//	printf("%d->%d %d\n",u,v,w);
	edge[++cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

ll dist[100005];
priority_queue <pll> Q;
void dijsktra(int sour){
	memset(dist,0x3f,sizeof(dist));
	dist[sour] = 0;
	Q.push(mkp(0,sour));
	while(!Q.empty()){
		pll cur = Q.top();
		Q.pop();
		if(dist[cur.second] < -cur.first) continue;
		int u = cur.second;
		for(int i = head[u];i;i = edge[i].nxt){
			int v = edge[i].to;
			if(dist[v] > dist[u] + edge[i].w){
				dist[v] = dist[u] + edge[i].w;
				Q.push(mkp(-dist[v],v));
			}
		}
	}
}
int dis[2][100005];
ll calc(int p){
	int r = p / d;
	ll sum = 1ll * d * (d + 1) / 2 * r;
	p %= d;
	sum += 1ll * (d + d - p + 1) * p / 2;
	return sum;
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d%d%d%d",&n,&m,&k,&d);
	rep(i,1,m){
		scanf("%d%d",&_u[i],&_v[i]);
		make(_u[i],_v[i],1);
		make(_v[i],_u[i],1);
	}
	dijsktra(n);
	rep(u,1,n) dis[0][u] = dist[u];
	dijsktra(k);
	rep(u,1,n) dis[1][u] = dist[u];

/*	rep(u,1,n) printf("%d ",dis[0][u]);
	printf("\n");
	rep(u,1,n) printf("%d ",dis[1][u]);
	printf("\n");	*/

//	printf("awa\n");
	cnt = 0;
	memset(head,0,sizeof(head));
	rep(i,1,m){
		if(dis[1][_u[i]] < d || _u[i] == 1) make(_u[i],_v[i],max(0,d - dis[1][_v[i]]));
		if(dis[1][_v[i]] < d || _v[i] == 1) make(_v[i],_u[i],max(0,d - dis[1][_u[i]]));
	}
	dijsktra(1);
	ll ans = linf;
	if(dis[1][n] < d) chkmin(ans,dist[n]);
	rep(u,1,n){
		if(dis[1][u] < d) continue;
//		printf("u=%d %lld\n",u,calc(dis[0][u] + 1));
		chkmin(ans,dist[u] + calc(dis[0][u] + 1));
	}
	printf("%lld\n",ans);
	return 0;
}