#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> Pii;
typedef pair<Pii, string> Pis;

struct Edge {
  int to, cost;  
};

int N, M, K, P;
vector<int> s, t;
vector<int> ss[1000];
vector<int> tt[1000];
vector<Edge> G[1000];

int dij() {
  priority_queue<Pis, vector<Pis>, greater<Pis> > Q;
  map<string, bool> used[N];
  string ini = "";
  string ends = "";
  for ( int i = 0; i < K; i++ ) {
    ini += "0";
    ends += "2";
  }

  for ( int j = 0; j < (int)ss[P].size(); j++ ) {
    if ( ini[ss[P][j]] == '0' ) ini[ss[P][j]] = '1';    
  }
  for ( int j = 0; j < (int)tt[P].size(); j++ ) {
    if ( ini[tt[P][j]] == '1' ) ini[tt[P][j]] = '2';	
  }
  
  Q.push(Pis(Pii(0, P), ini));
  
  while ( !Q.empty() ) {    
    Pis p = Q.top(); Q.pop();    
    int c = p.first.first;
    int n = p.first.second;
    string sta = p.second;
    //cout << n << " " << c << " "  << sta << endl;
    //cout << n << endl;
    if ( sta == ends ) return c;

    if ( used[n][sta] ) continue;
    used[n][sta] = true;

    for ( int i = 0; i < (int)G[n].size(); i++ ) {
      Edge e = G[n][i];
      int to = e.to, cost = e.cost;
      string nxt = sta;      
      for ( int j = 0; j < (int)ss[to].size(); j++ ) {
	if ( nxt[ss[to][j]] == '0' ) nxt[ss[to][j]] = '1';	
      }
      for ( int j = 0; j < (int)tt[to].size(); j++ ) {
	if ( nxt[tt[to][j]] == '1' ) nxt[tt[to][j]] = '2';	
      }
      Q.push(Pis(Pii(c+cost, to), nxt));      
    }
    //cout << n << endl;
  }

  return -1;
}

int main() {
  cin >> N >> M >> K >> P;
  P--;
  
  for ( int i = 0; i < M; i++ ) {
    int x, y, w;
    cin >> x >> y >> w;
    x--; y--;
    G[x].push_back(Edge{y, w});
    G[y].push_back(Edge{x, w}); 
  }
 
  s = vector<int>(K);
  t = vector<int>(K);
  for ( int i = 0; i < K; i++ ) {
    cin >> s[i] >> t[i];
    s[i]--; t[i]--;
    ss[s[i]].push_back(i);
    tt[t[i]].push_back(i);    
  } 
  
  int ans = dij();
  if ( ans == -1 ) cout << "Cannot deliver" << endl;
  else cout << ans << endl;
  
  return 0;
}

