#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int IINF = INT_MAX;
struct Edge { int src,dst,weight; };
struct Data {
  int cur,getBitmask,putBitmask,weight;
  bool operator < ( const Data &data ) const { return weight > data.weight; }
};
int V,E,k,sp,s[6],t[6],mindist[1001][1<<6][1<<6];
int drop[1001], target[1001];
vector<Edge> G[1001];

void compute(){
  rep(i,V) rep(j,(1<<k)) rep(l,(1<<k)) mindist[i][j][l] = IINF;
  mindist[sp][0][0] = 0;
  priority_queue<Data> Q;
  Q.push((Data){sp,0,0,0});
  while( !Q.empty() ) {
    Data data = Q.top(); Q.pop();
    if( data.putBitmask == ((1<<k)-1) ) { cout << data.weight << endl; return; }
    rep(i,G[data.cur].size()){
      int next = G[data.cur][i].dst;
      int getBitmask = data.getBitmask;
      int putBitmask = data.putBitmask;
      if( drop[next] != -1 ) getBitmask |= (1<<drop[next]);
      if( target[next] != -1 && ( ( getBitmask >> target[next] ) & 1) ) putBitmask |= (1<<target[next]);
      if( mindist[next][getBitmask][putBitmask] > data.weight + G[data.cur][i].weight ) {
	mindist[next][getBitmask][putBitmask] = data.weight + G[data.cur][i].weight;
	Q.push((Data){next,getBitmask,putBitmask,data.weight+G[data.cur][i].weight});
      }
    }
  }
  puts("Cannot deliver");
}

int main(){
  memset(drop,-1,sizeof(drop));
  memset(target,-1,sizeof(target));
  cin >> V >> E >> k >> sp;
  --sp;
  rep(i,E) {
    int x,y,w;
    cin >> x >> y >> w;
    --x, --y;
    G[x].push_back((Edge){x,y,w});
    G[y].push_back((Edge){y,x,w});
  }
  rep(i,k) {
    cin >> s[i] >> t[i];
    --s[i], --t[i];
    drop[s[i]] = i;
    target[t[i]] = i;
  }
  compute();
  return 0;
}