#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#define INF 1e9
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;//????????????bit?????????

struct edge{
  int to, weight;
};

int dp[1000][5000];//vertex, bit
vector<edge> G[1000];
int drop[10], term[10];

piii init(int a, int b, int c){
  return piii(a, pii(b,c));
}

int update(int bit, int to, int k){
  for(int i = 0; i < k; i++){
    if(drop[i] == to){
      bit = bit | (1 << (2*i));
    }
  }
    
  for(int i = 0; i < k; i++){
    if(term[i] == to && 0 < (bit & (1 << 2*i) ) ){
      bit = bit | (1 << (2*i + 1));
    }
  }

  return bit;
}

int main(){
  int n,m,k,p;

  cin >> n >> m >> k >> p;
  p--;
  for(int i = 0; i < m; i++){
    int from;
    edge e;
    cin >> from >> e.to >> e.weight;
    from--;e.to--;
    G[from].push_back(e);
    G[e.to].push_back((edge){from, e.weight});
  }

  for(int i = 0; i < k; i++){
    cin >> drop[i] >> term[i];
    drop[i]--;term[i]--;
  }

  for(int i = 0; i < 1000; i++){
    for(int j = 0; j < 5000; j++){
      dp[i][j] = INF;
    }
  }

  priority_queue<piii, vector<piii>, greater<piii> > que;
  que.push(init(0, 0, p));
  dp[p][0] = 0;
  while(!que.empty()){
    piii pos = que.top();que.pop();
    int cost = pos.first;
    int bit = pos.second.first;
    int v = pos.second.second;
    // cout << "cost:" << cost << " ";
    // cout << " bit:" << bit  << " ";
    // cout << "   v:" << v    << endl;
    // cout << "G[" << v << "].size():" << G[v].size() << endl;
    // cout << "dp[" << v << "][" << bit << "]:" <<
    //   dp[v][bit] << endl;

    if(bit == (1 << (2*k) ) - 1){
      cout << cost << endl;
      return 0;
    }

    for(int i = 0; i < G[v].size(); i++){
      int new_bit = update(bit, G[v][i].to, k);
      if(G[v][i].weight + cost < dp[G[v][i].to][new_bit]){
        dp[G[v][i].to][new_bit] = G[v][i].weight + cost;
        que.push(init(dp[G[v][i].to][new_bit],
                      new_bit,
                      G[v][i].to) );
      }
    }
  }
  cout << "Cannot deliver" << endl;  
  return 0;
}