#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define debug(a) cout<<a<<'\n'
#define Pll pair<ll,ll>
#define PII pair<int,int>
#define ft first
#define sd second
#define vec vector
#define pushk push_back
#define ump unordered_map
#define pl p<<1
#define pr p<<1|1
using namespace std;
const int N = 1e5 + 10, M = 4e5 + 10, mod = 1e9 + 7;
const ll inf = 1e18;
const ld eps = 1e-13;
int mov[4][2] = { {0,1},{1,0},{-1,0},{0,-1} }, dx, dy, _ = 1, __ = 1;
void bout(bool f) {
	if (f)cout << "Yes\n";
	else cout << "No\n";
}
ll n, m, k,d;
int h[N],e[M],ne[M],idx;
void link(int x,int y){
	e[++idx]=y;
	ne[idx]=h[x];
	h[x]=idx;
}

ll dt[N],ds[N],dk[N];

void dij(ll d[],int u){
	memset(d,0x3f,sizeof dt);
	d[u]=0;
	ll dist,id;
	priority_queue<Pll,vector<Pll>,greater<Pll>>q;
	q.push({0,u});
	while(!q.empty()){
		dist=q.top().ft;
		id=q.top().sd;
		q.pop();
		if(d[id]<dist)continue;
		for(int i=h[id];~i;i=ne[i]){
			int v=e[i];
			if(d[v]>d[id]+1){
				d[v]=d[id]+1;
				q.push({d[v],v});
			}
		}
	}
}

ll cul(int dist){
	ll x,y;
	x=dist/d*d*(d+1)/2;
	y=dist%d;
	return x+y*(2*d-y+1)/2;
}

void ini() {

}
void solve() {
	cin>>n>>m>>k>>d;
	memset(h,-1,sizeof h);idx=0;
	ll x,y,z;
	for(int i=1;i<=m;++i){
		cin>>x>>y;
		link(x,y);
		link(y,x);
	}
	dij(dt,n);
	dij(dk,k);
	ll ans=cul(dt[1]);
	if(dk[1]>d)cout<<dt[1];
	else{
		memset(ds,0x3f,sizeof ds);
		ds[1]=0;
		priority_queue<Pll,vec<Pll>,greater<Pll>>q;
		q.push({0,1});
		ll dist,u;
		while(!q.empty()){
			dist=q.top().ft;
			u=q.top().sd;
			q.pop();
			if(dist>ds[u])continue;
			for(int i=h[u];~i;i=ne[i]){
				int v=e[i];
				x=d-dk[v];
				if(x>=1){
					if(ds[v]>ds[u]+x){
						ds[v]=ds[u]+x;
						q.push({ds[v],v});
					}
				}else if(x==0&&(dk[1]!=d||u!=1)){
					if(ds[v]>ds[u])ds[v]=ds[u];//外圈 
				}
			}
		}
		for(int i=1;i<=n;++i){
			if(dk[i]==d){
				ans=min(ans,ds[i]+cul(dt[i]+1));
			}
		}
		if(dk[n]<d)ans=min(ans,ds[n]);
	}
	cout<<ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	streambuf* cinbackup = cin.rdbuf(), * coutbackup = cout.rdbuf();
	ifstream fin("in.txt");
	ofstream fout("out.txt");
	cin.rdbuf(fin.rdbuf());
	cout.rdbuf(fout.rdbuf());
#endif
	//cin >> _;
	__ = _;
	ini();
	while (_--) {
		solve();
	}
	return 0;
}