#include <bits/stdc++.h>
using namespace std;
const int INF = 1000*1000 * 2;

struct Cost{
  int pos;
  int state;
  int cost;
  Cost():pos(0),state(0),cost(0){}
  Cost(int pos, int state, int cost):pos(pos),state(state),cost(cost){}
  bool operator<(const Cost& a)const{
    return cost > a.cost;
  }
};

struct Node{
  int to;
  int cost;
  Node():to(0),cost(0){}
  Node(int to, int cost):to(to),cost(cost){}
};

int jIsS(const int j, const vector<int>& S){
  for(unsigned int i = 0; i < S.size(); i++){
    if(S[i] == j){
      return i;
    }
  }
  return -1;
}

int jIsT(const int j, const vector<int>& T){
  for(unsigned int i = 0; i < T.size(); i++){
    if(T[i] == j){
      return i;
    }
  }
  return -1;
}

void dijkstra(const int node, const int edge, const int env, const int start, const vector< vector<Node> >& G, vector<int>& S, const vector<int>& T){
  int n_state = 1 << (2*env);
  int d[n_state][node];
  for(int i = 0; i < n_state; i++){
    for(int j = 0; j < node; j++){
      d[i][j] = INF;
    }
  }
  d[0][start] = 0;

  priority_queue< Cost > que;
  que.push(Cost(start, 0, 0));
  while(!que.empty()){
    Cost q = que.top(); que.pop();
    int mini = q.state;
    int minj = q.pos;
    //if(q.cost > d[mini][minj]) continue;
    for(unsigned int j = 0; j < G[minj].size(); j++){
      int to = G[minj][j].to;
      int cost = G[minj][j].cost;
      int Sidx = jIsS(to, S);
      int Tidx = jIsT(to, T);
      int state = mini;
      if(Sidx != -1){
        state = mini | (1 << Sidx);
      }
      if(Tidx != -1 && ((mini >> Tidx)&1)){
        state = mini | (1 << (env + Tidx));
      }
      if( d[state][to] > d[mini][minj] + cost ){
        d[state][to] = d[mini][minj] + cost;
        que.push( Cost(to, state, d[state][to]) );
      }
      /*
      if( Sidx != -1 ){
        state = mini | (1 << Sidx);
        d[mini | (1 << Sidx)][to] = min(d[mini | (1 << Sidx)][to],  d[mini][minj] + cost );
        que.push(Cost(to, mini | (1 << Sidx), d[mini | (1 << Sidx)][to]));
      }else if( Tidx != -1 ){
        if( mini & (1 << Tidx) ){
          state = mini | (1 << (env + Tidx));
          d[mini | (1 << (env + Tidx))][to] = min(d[mini | (1 << (env + Tidx))][to], d[mini][minj] + cost);
          que.push( Cost(to, mini | (1 << (env + Tidx)), d[mini | (1 << (env + Tidx))][to]) );
        }
      }
      if( d[mini][to] > d[mini][minj] + cost ){
        d[mini][to] = d[mini][minj] + cost;
        que.push( Cost(to, mini, d[mini][to]) );
      }
      */
    }
  }

  /*
  for(int i = 0; i < n_state; i++) for(int j = 0; j < node; j++){
    cout << bitset<4>(i) << " " << j << " = ";
    cout << d[i][j] << endl;
  }
  */

  int ans = INF;
  for(int j = 0; j < node; j++){
    ans = min(ans, d[(1<<(2*env))-1][j]);
  }

  if(ans == INF) cout << "Cannot deliver" << endl;
  else cout << ans << endl;
}

int main(void){
  int n, m, k, p; cin >> n >> m >> k >> p;
  p--;
  vector< vector<Node> > G(n);
  for(int i = 0; i < m; i++){
    int x, y, w; cin >> x >> y >> w;
    x--; y--;
    G[x].push_back(Node(y, w));
    G[y].push_back(Node(x, w));
  }
  vector<int> S(k), T(k);
  for(int i = 0; i < k; i++){
    int s, t; cin >> s >> t;
    s--; t--;
    S[i] = s;
    T[i] = t;
  }

  dijkstra(n, m, k, p, G, S, T);
  return 0;
}

Measured memory_bytes: 19908