#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

vector<vector<ll>> dist(1010, vector<ll>(1010, 1e9));

void dijkstra(int s, vector<vector<P>> &G){
    priority_queue<P, vector<P>, greater<P>> que;
    dist[s][s] = 0;
    que.emplace(0, s);

    while(que.size()){
        ll ccost, cv;
        tie(ccost, cv) = que.top();
        que.pop();

        if(dist[s][cv] < ccost) continue;

        for(auto x : G[cv]){
            ll nv, ncost;
            tie(nv, ncost) = x;
            
            if(dist[s][cv] + ncost < dist[s][nv]){
                dist[s][nv] = dist[s][cv] + ncost;
                que.emplace(dist[s][nv], nv);
            }
        }
    }
}

int main(){
    int n, m, k, p; cin>>n>>m>>k>>p;
    p--;
    vector<vector<P>> G(n);
    for(int i=0; i<m; i++){
        int x, y, w; cin>>x>>y>>w;
        x--, y--;
        G[x].emplace_back(y, w);
        G[y].emplace_back(x, w);
    }

    for(int i=0; i<n; i++){
        dijkstra(i, G);
    }

    vector<int> s(k), t(k);
    vector<int> v;
    for(int i=0; i<k; i++){
        cin>>s[i]>>t[i];
        s[i]--, t[i]--;
        v.emplace_back(i);
        v.emplace_back(i);
    }

    ll ans = 1e18;
    do{
        ll sum = dist[p][s[v[0]]];
        bool valid = true;
        if(sum == 1e9) valid = false;
        vector<int> visited(k, 0);
        visited[v[0]]++;
        for(int i=0; i<2*k-1; i++){
            ll cdist = 0;
            if(visited[v[i+1]] == 0){
                if(visited[v[i]] == 1){
                    cdist = dist[s[v[i]]][s[v[i+1]]];
                }
                else{
                    cdist = dist[t[v[i]]][s[v[i+1]]];
                }
            }
            else{
                if(visited[v[i]] == 1){
                    cdist = dist[s[v[i]]][t[v[i+1]]];
                }
                else{
                    cdist = dist[t[v[i]]][t[v[i+1]]];
                }
            }

            visited[v[i+1]]++;

            if(cdist == 1e9) valid = false;
            else sum += cdist;
        }

        if(valid) ans = min(ans, sum);

    }while(next_permutation(v.begin(), v.end()));

    if(ans == 1e18){
        cout << "Cannot deliver" << endl;
    }
    else{
        cout << ans << endl;
    }
}
