#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <cmath>
#include <climits>
#include <queue> 
#include <cstdio>

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

using namespace std;

struct Edge {
  int src,dst,weight;
};

struct Data {
  int cur,weight;
  bool operator < ( const Data &data ) const {
    return weight > data.weight;
  }
};

const int IINF = INT_MAX;
const int MAXV = 1010;
int V,E,k,sp,s[10],t[10];
vector<Edge> G[MAXV];
int mindist[MAXV][MAXV];
vector<int> vs;

void dijkstra(int a){ // a -> start point
  rep(i,V) mindist[a][i] = IINF;
  priority_queue<Data> Q;
  Q.push((Data){a,0});
  mindist[a][a] = 0;
  while( !Q.empty() ){
    Data data = Q.top(); Q.pop();
    if( mindist[a][data.cur] < data.weight ) continue;
    rep(i,G[data.cur].size()){
      int next = G[data.cur][i].dst;
      if( mindist[a][next] > data.weight + G[data.cur][i].weight ) {
	mindist[a][next] = data.weight + G[data.cur][i].weight;
	Q.push((Data){next,mindist[a][next]});
      }
    }
  }
}

struct Data2 {
  int cur,weight,took,fin;
  bool operator < ( const Data2 &data ) const {
    if( weight != data.weight ) return weight > data.weight;
    if( cur != data.cur ) return cur > data.cur;
    if( fin != data.fin ) return fin > data.fin;
    return took > data.took;
  }
};

int mindist2[20][1<<7][1<<7];

void dijkstra2(){

  rep(i,vs.size()) rep(j,1<<7) rep(k,1<<7) mindist2[i][j][k] = IINF;

  map<int,int> mp[2],vsmp;

  rep(i,vs.size()) vsmp[vs[i]] = i;
  rep(i,k) {
    mp[0][s[i]] = i;
    mp[1][t[i]] = i;
  } 

  priority_queue<Data2> Q;
  int temp1 = 0, temp2 = 0;
  Q.push((Data2){sp,0,temp1,temp2});

  bool success = true;
  rep(i,k) if( mindist[sp][t[i]] == IINF || mindist[sp][s[i]] == IINF ) {
    success = false;
    break;
  }
  if( !success ) {
    puts("Cannot deliver");
    return;
  }
  while( !Q.empty() ){
    Data2 data = Q.top(); Q.pop();

    if( data.fin == ((1<<k)-1) ) {
      cout << data.weight << endl;
      return;
    }

    if( mindist2[vsmp[data.cur]][data.took][data.fin] < data.weight ) continue;
 
   rep(i,vs.size()){
      int next = vs[i];
      if( next == data.cur ) continue;
      int took = data.took, fin = data.fin;
      if( mp[0].count(next) ) took |= (1<<mp[0][next]);
      if( mp[1].count(next) && ( ( took >> mp[1][next] ) & 1 ) ) fin  |= (1<<mp[1][next]);

      if( mindist2[vsmp[next]][took][fin] > data.weight + mindist[data.cur][next] ) {

	mindist2[vsmp[next]][took][fin] = data.weight + mindist[data.cur][next];
	Q.push((Data2){next,mindist2[vsmp[next]][took][fin],took,fin});
      }
    }

  }
  puts("Cannot deliver");
}

void compute(){
  rep(i,vs.size()) dijkstra(vs[i]);
  dijkstra2();
}

int main(){

  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});
  }

  vs.push_back(sp);
  rep(i,k){
    cin >> s[i] >> t[i];
    --s[i], --t[i];
    vs.push_back(s[i]);
    vs.push_back(t[i]);
  }

  sort(vs.begin(),vs.end());
  vs.erase(unique(vs.begin(),vs.end()),vs.end());

  compute();

  return 0;
}