/*
    author:  Maksim1744
    created: 28.03.2024 12:17:44
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

template<typename T>
using pq = priority_queue<T, vector<T>, greater<T>>;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, m, k, d;
    cin >> n >> m >> k >> d;
    --k;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    auto bfs = [&](int v) {
        vector<int> d(n, 1e9);
        d[v] = 0;
        queue<int> q;
        q.push(v);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int k : g[v]) {
                if (d[k] > d[v] + 1) {
                    d[k] = d[v] + 1;
                    q.push(k);
                }
            }
        }
        return d;
    };

    auto cost = bfs(k);
    for (int& x : cost)
        x = max(0, d - x);
    show(cost);
    vector<bool> covered(n);
    covered[0] = true;
    for (int i = 0; i < n; ++i) {
        if (cost[i] > 0)
            covered[i] = true;
    }

    auto fin = bfs(n - 1);
    vector<ll> path_cost(n + 5, 0);
    for (int i = 1; i < path_cost.size(); ++i) {
        path_cost[i] = path_cost[i - 1] + d - (i - 1) % d;
    }
    show(path_cost);

    ll ans = 1e18;
    pq<pair<ll, int>> q;
    vector<ll> dist(n, 1e18);
    q.emplace(0, 0);
    dist[0] = 0;

    while (!q.empty()) {
        auto [dd, v] = q.top();
        q.pop();
        if (dd != dist[v]) continue;
        if (!covered[v]) {
            show(v, dd, fin[v]);
            ans = min(ans, dd + path_cost[fin[v] + 1]);
            show(ans);
            continue;
        }
        for (int k : g[v]) {
            if (dist[v] + cost[k] < dist[k]) {
                dist[k] = dist[v] + cost[k];
                q.emplace(dist[k], k);
            }
        }
    }

    if (covered[n - 1])
        ans = min(ans, dist[n - 1]);
    cout << ans << '\n';

    return 0;
}