#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int INF = 1e9;

struct State{
  int pos, cost, bit1, bit2;
  State(int p, int c, int b1, int b2):pos(p), cost(c), bit1(b1), bit2(b2){};
};

int d[1010][1010];
vector<PII> info;

void wf(int n){
  for(int i = 0 ; i < n ; i++) d[i][i] = 0;
  
  for(int k = 0 ; k < n ; k++)
    for(int i = 0 ; i < n ; i++)
      for(int j = 0 ; j < n ; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
}

int solve(int p){
  int m = info.size();
  
  queue<State> que;
  que.push(State(p, 0, 0, 0));
  
  int ret = INF;
  
  while(!que.empty()){
    State q = que.front(); que.pop();
    
    if(q.cost >= ret) continue;
    
    if(__builtin_popcount(q.bit2) == m){
      ret = min(ret, q.cost);
      continue;
    }

    // pick
    for(int i = 0 ; i < (int)info.size() ; i++){
      if( !((1<<i) & q.bit1)) que.push(State(info[i].first, q.cost + d[q.pos][info[i].first], q.bit1 | (1<<i), q.bit2));
    }
    
    // send
    for(int i = 0 ; i < (int)info.size() ; i++){
      if( (1<<i) & q.bit1 && !((1<<i) & q.bit2)){
	que.push(State(info[i].second, q.cost + d[q.pos][info[i].second], q.bit1, q.bit2 | (1<<i)));
      }
    }
    
  }
  return ret;
}

int main(){
  for(int i = 0 ; i < 1010 ; i++)
    for(int j = 0 ; j < 1010 ; j++) d[i][j] = INF;


  int n, m, k, p;
  cin >> n >> m >> k >> p;
  p--;
  
  int from, to, w;
  for(int i = 0 ; i < m ; i++){
    cin >> from >> to >> w;
    from--, to--;
    d[from][to] = d[to][from] = w;
  }
  
  wf(n);
  
  for(int i = 0 ; i < k ; i++){
    cin >> from >> to;
    from--, to--;
    info.push_back(PII(from, to));
  }
  
  int ans = solve(p);
  if(ans == INF) cout << "Cannot deliver" << endl;
  else cout << ans << endl;

}