// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}
struct Edge{ int to, cost; };
typedef vector<Edge> Node;
typedef vector<Node> Graph;

typedef tuple<int, vector<int>> State;
typedef pair<int, State> Key;

int main(){
    iostream_init();
    int n, m, k, p;
    cin >> n >> m >> k >> p;
    p--;
    Graph G(n);
    REP(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }

    vector<int> S(k), T(k);
    REP(i, k) cin >> S[i] >> T[i];
    REP(i, k) S[i]--;
    REP(i, k) T[i]--;

    priority_queue<Key, vector<Key>, greater<Key>> que;
    map<State, int> memo;

    State init = make_tuple(p, vector<int>(k, 0));
    memo[init] = 0;
    que.push(make_pair(0, init));

    int ans = -1;
    while(!que.empty()) {
        int d; State state;
        tie(d, state) = que.top(); que.pop();
        int u; vector<int> b;
        tie(u, b) = state;

        if(b == vector<int>(k, 2)) {
            ans = d;
            break;
        }

        for(Edge edge : G[u]) {
            int nu = edge.to;
            int nd = d + edge.cost;
            vector<int> nb = b;
            REP(i, k) if(nb[i] == 0 && S[i] == nu) nb[i]++;
            REP(i, k) if(nb[i] == 1 && T[i] == nu) nb[i]++;
            State nstate = make_tuple(nu, nb);
            if(memo.count(nstate) && memo[nstate] <= nd) continue;
            memo[nstate] = nd;
            que.push(make_pair(nd, nstate));
        }
    }
    cout << (ans == -1 ? "Cannot deliver" : to_string(ans)) << endl;
    return 0;
}